A154238 Number of orbits of the action g*b = b o (g x g) of the group of permutations g of an n-element set S on the set of closed binary operations b on S.

1, 1, 10, 3411, 179228736, 2483590604688125, 14325593551925794051596768, 50976900379139614139041610902600299311, 155682086692129060007763454017522652304844346252853248

Offset: 0

Author

David Pasino, Jan 05 2009, Jan 08 2009, Jan 12 2009

Keywords

• nonn

Comments

Here are several different ways of expressing the condition that g*b = b:

b(u, v) = b(gu, gv) for all u, v in S.

The level sets of b are closed under g x g.

The level sets of b are unions of cycles of g x g.

The cycles of g x g are subsets of level sets of b.

b is constant on cycles of g x g.

There is no requirement for g to be an automorphism of b. Given g, the fixed b are determined by simply choosing a value in S for each cycle of g x g. The product b(u, v) is defined to be that constant value for every (u, v) in the cycle.

So the number of degrees of freedom for b is the number of cycles of g x g. How many cycles does g have on S x S? If u is in a c-cycle C and v is in a d-cycle D, then (u, v) is in an lcm(c, d)-cycle and C x D is partitioned into these cycles, so there must be cd/lcm(c, d) of them, which is gcd(c, d).

So letting s_k be the number of k-cycles of g on S for each k from 1 to n, the total number of cycles of g on S x S is the sum on k and j of gcd(k, j) s_k s_j. That's the number of degrees of freedom for b and each degree has valence n, so raise n to that power. Then multiply by the well-known number of permutations of type s, which is n! divided by the factorials of the s_k and by the powers k^s_k. Add this up over all the partitions of n and divide by n!.

Additional comments from Christian G. Bower: This is the number of nonisomorphic n-state relations on a set of n elements. If at the step of raising n to the power, we raised instead some constant m to that power, the formula would give the number of isomorphism classes of m-state relations on an n-element set.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..26

Crossrefs

Cf. k-state relations: A000595 for k=2, A004105 for k=3, A001374 for k=4, A053516 for k=5.

Cf. A001329, A091057.

Cf. A000595, A004105, A001374, A053516. - Vladeta Jovovic, Jan 06 2009

Formula

a(n) = Sum_{1*s_1 + 2*s_2 + ... = n} (fixA[s_1, s_2,..]/(1^s_1*s_1!*2^s_2*s2!* ...)) where fixA[s_1, s_2, ...] = n^(Sum_{i, j>=1} gcd(i, j)*s_i*s_j).

Extensions

Edited by Christian G. Bower and N. J. A. Sloane, Jan 08 2009