# How many non-isomorphic binary structures on the set of $n$ elements?

This question is originated from Fraleigh's Abstract Algebra, Ex3.34. The exercise is for the case of $n=2$. The answer is 10, and the below is my solution about it.

Let the set be $\{{ a,b \}}$. If we let $f$ be the non-identity isomorphism($f(a)=b, f(b)=a$), then 4 binary structures are invariant under $f$: If you set $a*a$ and $a*b$ then the rest are determined since $f(a)*f(a)=b*b$ and $f(a)*f(b)=b*a$. So the number of non-isomorphic binary structures is $4+ \frac {16-4} 2 = 10$.

Is there any generalization of this on $n$ elements? It seems a little complicated for me. I tried to find something on google, but I can't find out.

-
If you can compute the answer for $n = 3$ you can try looking it up in the OEIS. The obvious search terms didn't work but it may be filed under something other than "isomorphism classes of magmas." –  Qiaochu Yuan Jun 26 '11 at 14:39
Sounds extremely hard to do in general. –  David Kohler Jun 26 '11 at 21:26
@Qiaochu, computing for $n=3$ may not be so easy, at any rate if you try to do it by hand. I think we're talking about oeis.org/A001329 which says "The number of isomorphism classes of closed binary operations on a set of order n," but it also says "Number of nonisomorphic groupoids with n elements," and those "groupoids" throw me. –  Gerry Myerson Jun 26 '11 at 23:09
@Gerry: that is a now-deprecated (I think) term for magmas. –  Qiaochu Yuan Jun 26 '11 at 23:13
@Qiaochu, thanks. Hunting around the web a bit I got the impression "groupoid" was used in two different senses, and in one of those sense you only need a "partial binary operation," that is, the operation need not be defined on all pairs of elements of the underlying set. That's what threw me - if that's the kind of groupoid we're talking about, then A001329 is inappropriate. But I think OEIS is using the term in the magma sense, which is the sense relevant to this question (I think...). –  Gerry Myerson Jun 26 '11 at 23:49

Following up the citations at the OEIS page in my comment, it looks like much is to be learned from Michael A Harrison, The number of isomorphism types of finite algebras, Proc Amer Math Soc 17 (1966) 731-737. The formulas there are elementary but very long, so I won't type any of them out here. I believe the paper is freely available on the AMS website.

If the sources are saying what I think they're saying, for $n=3$ you get 3,330.

EDIT: In a comment, Doug asks about a formula at the OEIS page. I don't think it will fit in a comment, so I'll try to write it out here. Let $${\rm fix\ }A(s_1,s_2,\dots)=\prod_{i,j\ge1}\sum_{d\mid{\rm lcm}(i,j)}(ds_d)^{s_is_j\gcd(i,j)}$$ Then $$a_n=\sum_{s_1+2s_2+\dots=n}{{\rm fix\ }A(s_1,s_2,\dots)\over1^{s_1}s_1!2^{s_2}s_2!\dots}$$

-
Thanks! It tells us what is the formula, though very complicated. A quick link to it is here. –  Gobi Jun 27 '11 at 7:41

It seems to me important to point out that the above formula iterating over all partition shapes is not the best we can do. What we are looking for here is an enumeration of all $N\times N$ matrices with entries from $1$ to $N$ under the symmetric group acting on the entries and the rows and columns at the same time. We can use Burnside directly and calculate the appropriate cycle index (which represents the action of the symmetric group on ordered pairs) from the cycle index of the symmetric group, as was done at this MSE link. The cycle index of the symmetric group can be computed with a trick that goes back to Lovasz: $$Z(S_0) = 1 \quad \text{and} \quad Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l})$$ and we do not need to iterate over all partitions to compute this index.

Now Burnside is quite simple here. For each cycle of a single permutation $P$ of the matrix elements induced by the action of a permutation $Q$ from the symmetric group on $N$ elements we need to determine the assignments to the slots on the cycle that are fixed by $P$. But these are precisely the assignments that consist of cyclical repetitions of complete cycles from $Q$ i.e. we can place any cycle from $Q$ on a cycle from $P$ as long as the length of the former divides the length of the latter. Every such pair produces $q$ possible assignments where $q$ is the length of the cycle from $Q.$ This simple observation suffices to apply Burnside.

We get the following sequence of values: $$1, 10, 3330, 178981952, 2483527537094825, 14325590003318891522275680,\\ 50976900301814584087291487087214170039,\\ 155682086691137947272042502251643461917498835481022016,\\ 541851439802559836957713164869818405872834954135521300809902639457510935,\ldots$$ which agrees with the OEIS entry.

The above values were computed with the following Maple code.


with(numtheory);
with(group):
with(combinat):

pet_cycleind_symm :=
proc(n)
local p, s;
option remember;

if n=0 then return 1; fi;

end;

pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

terml := [];

cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;

[cf, terml];
end;

bs_binop :=
proc(n)
option remember;
local dsjc, flat, p, q, len,
cyc, cyc1, cyc2, l1, l2, res;

if n=0 then return 1; fi;
if n=1 then return 1; fi;

res := 0;

for dsjc in pet_cycleind_symm(n) do
flat := pet_flatten_term(dsjc);

p := 1;

for cyc1 in flat[2] do
l1 := op(1, cyc1);
for cyc2 in flat[2] do
l2 := op(1, cyc2);

len := lcm(l1,l2); q := 0;

for cyc in flat[2] do
if len mod op(1, cyc) = 0 then
q := q  + op(1, cyc);
fi;
od;

p := p * q^(l1*l2/len);
od;
od;

res := res + p*flat[1];
od;

res;
end;

-