| 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.
| 