5
$\begingroup$

Let $(M,\circ)$ be a magma over a finite set of order $n$. I tried to count all the possible magmas up to isomorphism, but I just can't get it right. My naive approach was to count all the possible Cayley tables, that is $n^{n^2}$ and trying to divide this figure by something. Now, what is this something? I guess it's related to $n!$ but my imagination stops here.

EDIT: I think, but might well be wrong, that the two following problems are equivalent restatements of the original problem.

graph-theoretical flavor: enumerate up to isomorphism all the bipartite graphs on the sets $A$ and $B$ such that $|A|=n^2$ and $|B|=n$ and every vertex in $A$ has degree one.

"ball-boxing" flavor: enumerate in how many ways one can distribute $n^2$ identical balls in $n$ identical boxes.

$\endgroup$
3
  • 1
    $\begingroup$ This may be tricky to enumerate. Using the Magma Maple package gives that the sequence starts $1, 1, 10, 3330, 178981952, \ldots$; the last of these has factorization $2^6\cdot 23 \cdot 121591$, which suggests more than just ratios of powers and factorials are involved. $\endgroup$ Oct 23, 2014 at 10:08
  • $\begingroup$ I see. I just wonder what mysterious hidden machinery makes many of these counting procedures so cumbersome and complicated... $\endgroup$ Oct 23, 2014 at 11:00
  • 1
    $\begingroup$ I think it's that the size of the isomorphism class depends very sensitively on the multiplication table. (It's not necessarily the case here, but) sometimes enumeration is just hard. $\endgroup$ Oct 23, 2014 at 11:17

1 Answer 1

2
$\begingroup$

A (very complicated) formula computing the number of isomorphism classes of magmas of a given, finite order appears in this article by M.A. Harrison. It is derived by understanding the action of the symmetric group $S_n$ on $n\times n$ Cayley tables and using evaluations of cycle index polynomials to derive the formula. See also this OEIS entry for other references and further values.

$\endgroup$
1
  • $\begingroup$ @marcotrevi The formula should be complicated, but the method should be fairly simple to explain: apply Burnside's lemma to the action of $S_n$. Then we need to determine, for any permutation $\pi$, which magmas on $\{1,2,\ldots n\}$ are invariant under $\pi$. This has some (not entirely trivial—double transitivity is involved) interpretation in terms of the cycle type of $\pi$. $\endgroup$ Oct 24, 2014 at 2:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .