OFFSET
0,3
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
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).
CROSSREFS
KEYWORD
nonn
AUTHOR
David Pasino, Jan 05 2009, Jan 08 2009, Jan 12 2009
EXTENSIONS
Edited by Christian G. Bower and N. J. A. Sloane, Jan 08 2009
STATUS
approved