17
$\begingroup$

I am studying Scott's book Group Theory. In the Exercise $1.1.17$ he asks us to show that if $S$ is a set and $|S|=n$, then there are $n^{\frac{n^{2}+n}{2}}$ commutative binary operations on $S$. But he doesn't talk about how many associative binary operations there are on a finite set.

Is there an answer to that question? I mean, how many associative binary operations there are on a finite set?

$\endgroup$
7
$\begingroup$

Unlike the example you give (of commutative binary operations), there is no closed formula for the number of associative binary operations on a finite set.

A semigroup is a set with an associative binary operation. In what follows I will write "semigroup" rather than "associative binary operation".

It is shown in

Kleitman, Daniel J.; Rothschild, Bruce R.; Spencer, Joel H. The number of semigroups of order n. Proc. Amer. Math. Soc. 55 (1976), no. 1, 227–232.

that almost all semigroups of order $n$ are $3$-nilpotent, and in Theorem 2.1(i) of

Distler, Andreas; Mitchell, J. D. The number of nilpotent semigroups of degree 3. Electron. J. Combin. 19 (2012), no. 2, Paper 51, 19 pp.

that the number of $3$-nilpotent semigroups of order $n$ is: \begin{equation} \sigma(n)=\sum_{m=2}^{a(n)}{n \choose m}m\sum_{i=0}^{m-1}(-1)^i{m-1 \choose i}(m-i)^{\left((n-m)^2\right)} \end{equation} where $a(n)=\left\lfloor n+1/2-\sqrt{n-3/4}\,\right\rfloor$.

So, $\sigma(n)$ is approximately the number of distinct associative binary operations on a set of size $n$.

The value $\sigma(n)$ appears to converge very quickly to the number $\tau(n)$ of semigroups with $n$ elements: \begin{equation} \begin{array}{l|llllllll} n&1&2&3&4&5&6&7&8\\\hline \tau(n)& 1& 8& 113& 3492& 183732& 17061118& 7743056064& 148195347518186\\ \sigma(n)&0& 0& 6& 180& 11720& 3089250& 5944080072& 147348275209800 \end{array} \end{equation} So, by $n=8$, the ratio $\sigma(n)/\tau(n)>0.994$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.