cp's OEIS Frontend

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.

%I A154238 #18 Dec 19 2021 14:00:05
%S A154238 1,1,10,3411,179228736,2483590604688125,14325593551925794051596768,
%T A154238 50976900379139614139041610902600299311,
%U A154238 155682086692129060007763454017522652304844346252853248
%N 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.
%C A154238 Here are several different ways of expressing the condition that g*b = b:
%C A154238 b(u, v) = b(gu, gv) for all u, v in S.
%C A154238 The level sets of b are closed under g x g.
%C A154238 The level sets of b are unions of cycles of g x g.
%C A154238 The cycles of g x g are subsets of level sets of b.
%C A154238 b is constant on cycles of g x g.
%C A154238 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.
%C A154238 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).
%C A154238 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!.
%C A154238 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.
%H A154238 Alois P. Heinz, <a href="/A154238/b154238.txt">Table of n, a(n) for n = 0..26</a>
%F A154238 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).
%Y A154238 Cf. k-state relations: A000595 for k=2, A004105 for k=3, A001374 for k=4, A053516 for k=5.
%Y A154238 Cf. A001329, A091057.
%Y A154238 Cf. A000595, A004105, A001374, A053516. - _Vladeta Jovovic_, Jan 06 2009
%K A154238 nonn
%O A154238 0,3
%A A154238 _David Pasino_, Jan 05 2009, Jan 08 2009, Jan 12 2009
%E A154238 Edited by _Christian G. Bower_ and _N. J. A. Sloane_, Jan 08 2009