# How many associative binary operations there are on a finite set?

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?

#### Solutions Collecting From Web of "How many associative binary operations there are on a finite set?"

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:

\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)}

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{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}

So, by $n=8$, the ratio $\sigma(n)/\tau(n)>0.994$.