For two sets $O$ and $A$, we will call a *category structure* a collection of functions ${\sf dom}:A\to O,\ {\sf cod}:A\to O,\ {\sf 1}:O\to A,\ \circ:A\times\_OA\to A$ satisfying the usual axioms for a category.



> 
> Can we parametrize the number of category structures (up to iso or equivalence) on two sets $O$ and $A$ in terms of their cardinalities? If a closed-form solution is too much to ask, can we get asymptotics for finite sets?
> 
> 
> 


Denote by ${\sf Cat}^\cong(n,m)$ the number of isomorphism classes of category structures on two sets $O$ and $A$ as above with $|O|=n$ and $|A|=m$. We trivially have that $n\leq m$. For $n=m=0$ we have exactly [one category](https://ncatlab.org/nlab/show/empty+category), and for $n=m=1$ we have a [unique up to iso category](https://ncatlab.org/nlab/show/terminal+category). In general for $n=m$ we have [${\sf Cat}^\cong(n,m)=1$](https://ncatlab.org/nlab/show/discrete+category), but all these observations are trivial.


For $n=1$ and $1\leq m$ we are counting the number of monoids on a set with $m$ elements, which I tried to search but was unable to find -- I did find this [related question](https://mathoverflow.net/questions/235494/how-many-monoids-with-n-arrows-exist), and the comments by Qiaochu Yuan give a lower bound of $B^\leq\_m\leq{\sf Cat}(1,m)$ where $B^\leq\_m$ is the $m^{th}$ [ordered Bell number](https://en.wikipedia.org/wiki/Ordered_Bell_number). As the comment by Douglas Zare suggests, this indicates that asymptotics are the best we should hope for since the ordered Bell numbers grow faster than exponential in $m$.


The case for semigroups is cutting edge for a set with $12$ elements by a [paper](https://link.springer.com/chapter/10.1007/978-3-642-33558-7_63) linked in the answer to the linked question, so any asymptotics will have to use the existence of units to hopefully shave things down. The [second linked paper](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p51/pdf) gives a closed-form solution for the number of nilpotent semigroups of degree $3$, so adding mild restrictions seems to potentially allow for more tractable counting.


Denote by ${\sf Cat}^\simeq(n,m)$ the number of equivalence classes of category structures on two sets $O$ and $A$ as above. We trivially have ${\sf Cat}^\simeq(n,m)\leq{\sf Cat}^\cong(n,m)$ with equality holding for $n=m$, but beyond this I don't see much concrete to say.


It may be useful to use the cardinalities of the hom-sets between objects in the category structures instead of the cardinality of the overall set of arrows, but beyond more obvious observations nothing jumps out at me using this approach either. For $1<n$ and $n<m$ it is trivial (and kind of fun) to count some small cases, but I don't know how to search the OEIS to see if the sequence is already catalogued. Any assistance is appreciated.




---


First linked paper: Distler A., Jefferson C., Kelsey T., Kotthoff L. (2012) The Semigroups of Order 10. In: Milano M. (eds) Principles and Practice of Constraint Programming. CP 2012. Lecture Notes in Computer Science, vol 7514. Springer, Berlin, Heidelberg. <https://doi.org/10.1007/978-3-642-33558-7_63>


Second linked paper: Distler A., Mitchell J. D., (2012) The Number of Nilpotent Semigroups of Degree 3. In: The Electronic Journal of Combinatorics, Volume 19, Issue 2 (2012). <https://doi.org/10.37236/2441>



How many category structures are possible on two sets?
The problem of counting semigroups and monoids of order $n$ up to isomorphism and anti-isomorphism (i.e., contravariant equvialence) is a very classical problem whose answer is conjectured but nobody has made serious progress in proving over the last 60 years. The analogous situation in group theory is that virtually all finite group theorists agree that the vast majority of groups of order less than or equal to $n$ are $p$-groups and likely $2$-groups, but nobody knows how to prove it.


A semigroup is called *$3$-nilpotent* if it has a zero (aka absorbing element) and the product of any $3$ elements is zero. Notice that you build a table in which the product of any three elements is zero, then automatically the associative law is satisfied and so it is very very easy to build such semigroups. In 1976, [Kleitman, Rothschild and Spencer](https://www.jstor.org/stable/2041879?seq=1) showed that asymptotically all associative multiplication tables on the set $\{1,\ldots, n\}$ are $3$-nilpotent. This is not counting up to isomorphism but the feeling is that these kinds of semigroups admit few automorphisms and so that is not overcounting by much.


So the conjecture that has been around forever is the proportion of semigroups of order $n$ which are $3$-nilpotent is $1$. In a beautiful paper [Distler and Mitchell](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p51) gave a closed formula for the number of $3$-nilpotent semigroups up to isomorphism and also up to isomorphism and anti-isomorphism. So conjecturaly this is the asymptotics for the number of finite semigroups. But nobody knows how to prove this conjecture. To the best of my knowledge, but I am a few years out of date, we only know the number of semigroups of order up to 10. The number of semigroups of order up to 10 has been counted up to isomorphism and anti-isomorphism in [Distler et al](https://link.springer.com/chapter/10.1007/978-3-642-33558-7_63) and it is the astronomical number 12,418,001,077,381,302,684. Almost all of these are $3$-nilpotent.


So what does this have to do with counting categories? Well, a one object category is a monoid and natural equivalence is isomorphism (and anti-isomorphism is contravariant equivalence) so this is a special case of the problem. Ah, but you are doing semigroups and we don't like semigroups because they don't even know who they are, lacking an identity (bad pun alert). Well, if you adjoin an identity you get an embedding from the set of isomorphism classes of semigroups of order $n-1$ into the set of isomorphism classes of monoids of order $n$ (same with isomorphism/anti-isomorphism classes). So the number of monoids of order $n$ up to isomorphism is at least as big as the number of semigroup of order $n-1$. Now I would conjecture that almost all monoids of order $n$ arise this way and so the number of monoids of order $n$ should behave like the number of $3$-nilpotent semigroups of order $n-1$. But again this is conjectural. I don't know if this monoid version of the conjecture has been published anywhere and since we don't have conferences these days I can't really ask around. So here is some evidence. In [Distler et al](https://link.springer.com/article/10.1007/s00233-013-9504-9) it is shown that the number of isomorphism/anti-isomorphism classes of semigroups of order $9$ is 52,989,400,714,478. The number of isomorphism/anti-isomorphism classes of monoids of order $10$ is computed in [Distler et al](https://link.springer.com/article/10.1007/s10472-009-9140-y) to be 52,991,253,973,742.


So in summary, we most likely know the asymptotics for monoids of order $n$ but it may be 100 years before anybody proves it.


**Added.** It was suggested in the comments to count Morita equivalence classes of categories instead, but that doesn't help the matter because two finite monoids are Morita equivalent of and only if they are isomorphic. The indecomposable projective right $M$-sets are of the form $eM$ with $e$ idempotent and any Morita equivalent monoid must be isomorphic to one of the form $eMe$ for a projective generator $eM$ of $M$-sets. But if $e\neq 1$, then $|eM|<|M|$ and so cannot generate $M$.


