Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
Knowing how many associative binary operations there are on a set with $n$ elements would tell you how many non-isomorphic semigroup structures there are on a set with $n$ elements. As far as I know, there is no known closed formula; a recent (2010) thesis gives the number of non-isomorphic, non-anti-isomorphic semigroups with $9$ elements as 52,989,400,714,478. –  Arturo Magidin Feb 3 '12 at 21:38
10  
    
@ArturoMagidin: Thanks for the references. –  spohreis Feb 3 '12 at 22:58
3  
@spohreis: On this site, Doug Spoonwood once asked whether the proportion of associative binary operations to total operations approached $0$ as $n$ gets large. I gave an answer that you can find here. But the estimate I gave is very weak, just enough to show that the limit is $0$. –  André Nicolas Feb 4 '12 at 0:51

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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