I can, with Edwin Clark's permission, forward to Frank my complete
correspondance with Edwin Clark about category enumeration via careful
definition.  I am asked not to cut & paste out of
context.  But my emails to Franklin T. Adams-Watters alone went
astray, for whatever reason. so I am not sure what to do.  I've
also asked some Haskell programming experts about Frank's enumeration
question (properly citing Frank), as Haskell has monads and functors
and other categorical stuff built in.  I'll share any useful
answers that I get.<br><br><div><span class="gmail_quote">On 11/23/06, <b class="gmail_sendername">Roland Bacher</b> <<a href="mailto:Roland.Bacher@ujf-grenoble.fr">Roland.Bacher@ujf-grenoble.fr</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>I realised that the formula below for enumerating categories<br>using quivers is completely wrong. It gives only an upper bound<br>since one has to require moreover associativity for the composition of<br>morphisms. The quiver approach works however in principle but
<br>is much more complex (and I guess this approach has been<br>used in some of the previous approaches).   Roland Bacher<br><br>On Thu, Nov 23, 2006 at 12:10:51PM -0800, Jonathan Post wrote:<br>> *"Formalized Proof, Computation, and the Construction Problem in Algebraic
<br>> geometry", by Carlos Simpson.<br>><br>> [PDF]* arXiv:*math*.AG/0410224 v1 8 Oct<br>> 2004<<a href="http://arxiv.org/pdf/math/0410224">http://arxiv.org/pdf/math/0410224</a>> File<br>> Format: PDF/Adobe Acrobat - View as
<br>> HTML<<a href="http://72.14.253.104/search?q=cache:8FWyl8lGqRwJ:arxiv.org/pdf/math/0410224+%22how+many+categories%22+math+theory&hl=en&gl=us&ct=clnk&cd=5">http://72.14.253.104/search?q=cache:8FWyl8lGqRwJ:arxiv.org/pdf/math/0410224+%22how+many+categories%22+math+theory&hl=en&gl=us&ct=clnk&cd=5
</a>><br>> finite integer N, *how many categories* are there with N morphisms? What *<br>> ...* Algebraic *theory* of machines, I. Trans. Amer. *Math*. Soc. 116<br>> (1965), 450-464.<br>><br>><br>><br>
> On 11/23/06, Jonathan Post <<a href="mailto:jvospost3@gmail.com">jvospost3@gmail.com</a>> wrote:<br>> ><br>> >Roland Bacher correctly refers to quivers as summarized in wikipedia at<br>> ><br>
> ><a href="http://en.wikipedia.org/wiki/Quiver_%28mathematics%29">http://en.wikipedia.org/wiki/Quiver_%28mathematics%29</a><br>> ><br>> >On 11/22/06, Roland Bacher < <a href="mailto:Roland.Bacher@ujf-grenoble.fr">
Roland.Bacher@ujf-grenoble.fr</a>> wrote:<br>> >><br>> >><br>> >> This numbers can also be obtained as the numbers<br>> >> of the following quotients of quivers:<br>> >><br>
> >> Associate to a category with n morphisms and k objects<br>> >> the quiver with k vertices corresponding to the objects<br>> >> and a(X,Y) arrows directed from the object X to the object<br>
> >> Y if there are a(X,Y) morphisms from X into Y.<br>> >><br>> >> Given two morphism g:X-->Y, f:Y-->Z with composition<br>> >> h=f o g:X-->Z, put the relation gf=h on the quiver algebra
<br>> >><br>> >> The resulting quotient algebra has dimension n and a basis<br>> >> given by the (simple) arrows.<br>> >><br>> >> This leads to the following "algorithm" for enumerating
<br>> >> all categories with n morphisms and k objects:<br>> >><br>> >> (a) enumerate all quivers (directed graphs) with k vertices and<br>> >> n oriented edges.<br>> >><br>> >> (b) Associate the following "weight" to such a quiver as follows :
<br>> >><br>> >> (b1)given a triplet of vertices X,Y,Z,<br>> >> set w(X,Y,Z)=(a(X,Z))^{a(X,Y) \cdot a(Y,Z)}<br>> >> (this counts the number of ways which associate a morphism<br>> >> X-->Z to a composition X-->Y-->Z) where a(U,V) denotes the
<br>> >> number of oriented arrows starting at U and ending at W.<br>> >><br>> >> (b2) associate to a given quiver the weight<br>> >> \prod_{X,Y,Z} w(X,Y,Z)<br>> >> where the product is over all triplets of vertices.
<br>> >><br>> >> The total sum of such weighted quivers yields then the solution.<br>> >><br>> >> Roland Bacher<br>> >><br>> >><br>> >><br>> >><br>> >>
<br>> >><br>> >> On Wed, Nov 22, 2006 at 04:20:32PM -0500, <a href="mailto:franktaw@netscape.net">franktaw@netscape.net</a> wrote:<br>> >> > How many categories are there?<br>> >> >
<br>> >> > First, how many categories are there with n morphisms and k objects?<br>> >> > This table starts:<br>> >> ><br>> >> > 1<br>> >> > 2  1<br>> >> > 7  3 1
<br>> >> > 35 16 3 1<br>> >> ><br>> >> > The first column is A058129, the number of monoids; the main diagonal<br>> >> > is all 1's.  I am not<br>> >> > 100% certain of the 16 in the final row.
<br>> >> ><br>> >> > Taking the row sums, we get:<br>> >> ><br>> >> > 1,3,11,55<br>> >> ><br>> >> > the number of categories with n morphisms.  This is probably not in
<br>> >> the<br>> >> > OEIS (only<br>> >> > A001776 is possible - other matches become less than A058129).  The<br>> >> > inverse Euler<br>> >> > transform,<br>> >> >
<br>> >> > 1,2,8,41<br>> >> ><br>> >> > is the number of connected categories with n morphisms; this is<br>> >> > likewise probably not<br>> >> > in the OEIS (only A052447 is possible).
<br>> >> ><br>> >> > Can somebody generate more data?<br>> >> ><br>> >> > Franklin T. Adams-Watters<br>> >> ><br>> >> > A category is a collection of objects and morphisms; each morphism is
<br>> >> > from one object<br>> >> > to another (not necessarily different) object.  Where the destination<br>> >> > of one morphism<br>> >> > is the source of a second, their composition is defined; composition
<br>> >> is<br>> >> > associative where<br>> >> > it is defined.  Each object has an identity morphism, which connects<br>> >> it<br>> >> > to itself; this<br>> >> > is an identity when composed with morphisms coming in and with
<br>> >> > morphisms going<br>> >> > out.<br>> >> ><br>> >> ________________________________________________________________________<br>> >> > Check Out the new free AIM(R) Mail -- 2 GB of storage and
<br>> >> > industry-leading spam and email virus protection.<br>> >> ><br>> >><br>> ><br>> ><br></blockquote></div><br>