How many monoids with strictly $n$ arrows exist? Is this known? I ask this only out of curiosity. Looking at $n=1,2,3,4$, this number doesn't appear to be very large relative to $n$.
8
-
$\begingroup$ It seems what is known is in the OEIS entry oeis.org/A058129 , linked to in the previous question mathoverflow.net/questions/159882/… $\endgroup$– j.c.Commented Apr 6, 2016 at 16:22
-
3$\begingroup$ Looking at $n = 1, 2, 3, 4$ seems like a terrible way to figure out the asymptotic behavior in $n$. Here is a lower bound: any poset with joins with $n$ elements describes a monoid with $n$ elements (an idempotent commutative monoid) where join is the monoid operation. An easy way to write down one of these is to write down a function $f : [n] \to \mathbb{N}$ and declare that $x \le y$ iff $f(x) \le f(y)$ (in other words a graded poset where every element of a grade is greater than every element of the previous grade). The number of these is the number of ordered set partitions of $n$, which.. $\endgroup$– Qiaochu YuanCommented Apr 6, 2016 at 16:33
-
2$\begingroup$ is counted by the ordered Bell numbers (en.wikipedia.org/wiki/Ordered_Bell_number): these grow faster than exponential in $n$. $\endgroup$– Qiaochu YuanCommented Apr 6, 2016 at 16:34
-
$\begingroup$ I am not really interested in asymptotic behavior so much as a closed form solution. Still, this is very interesting. Thank you. $\endgroup$– sergeant jamCommented Apr 6, 2016 at 17:16
-
7$\begingroup$ Why would you expect that a closed form solution exists? Asymptotic bounds seem more reasonable. $\endgroup$– Douglas ZareCommented Apr 6, 2016 at 18:38
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
Andreas Distler and his coauthors are the record holders. https://link.springer.com/chapter/10.1007/978-3-642-33558-7_63 gives the number up to 10 for semigroups (12,418,001,077,381,302,684 up to isomorphism and anti-isomorphism) though I thought I once heard a talk with bigger numbers like 11 or 12. You need to use some theory to get this far because the numbers are huge.
This paper http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p51 by Distler and Mitchell gives the number of 3-nilpotent semigroups for any n. Since this is most likely the vast majority they precompute this.
answered Apr 6, 2016 at 18:54