Categories

[Roland Bacher]

This numbers can also be obtained as the numbers
of the following quotients of quivers:

Associate to a category with n morphisms and k objects 
the quiver with k vertices corresponding to the objects 
and a(X,Y) arrows directed from the object X to the object
Y if there are a(X,Y) morphisms from X into Y.

Given two morphism g:X-->Y, f:Y-->Z with composition
h=f o g:X-->Z, put the relation gf=h on the quiver algebra

The resulting quotient algebra has dimension n and a basis
given by the (simple) arrows.

This leads to the following "algorithm" for enumerating
all categories with n morphisms and k objects:

(a) enumerate all quivers (directed graphs) with k vertices and
n oriented edges.

(b) Associate the following "weight" to such a quiver as follows :

(b1)given a triplet of vertices X,Y,Z,
set w(X,Y,Z)=(a(X,Z))^{a(X,Y) \cdot a(Y,Z)}
(this counts the number of ways which associate a morphism
X-->Z to a composition X-->Y-->Z) where a(U,V) denotes the 
number of oriented arrows starting at U and ending at W.

(b2) associate to a given quiver the weight 
\prod_{X,Y,Z} w(X,Y,Z)
where the product is over all triplets of vertices.

The total sum of such weighted quivers yields then the solution.

Roland Bacher



   


On Wed, Nov 22, 2006 at 04:20:32PM -0500, franktaw at netscape.net wrote:
> How many categories are there?
> 
> First, how many categories are there with n morphisms and k objects?  
> This table starts:
> 
> 1
> 2  1
> 7  3 1
> 35 16 3 1
> 
> The first column is A058129, the number of monoids; the main diagonal 
> is all 1's.  I am not
> 100% certain of the 16 in the final row.
> 
> Taking the row sums, we get:
> 
> 1,3,11,55
> 
> the number of categories with n morphisms.  This is probably not in the 
> OEIS (only
> A001776 is possible - other matches become less than A058129).  The 
> inverse Euler
> transform,
> 
> 1,2,8,41
> 
> is the number of connected categories with n morphisms; this is 
> likewise probably not
> in the OEIS (only A052447 is possible).
> 
> Can somebody generate more data?
> 
> Franklin T. Adams-Watters
> 
> A category is a collection of objects and morphisms; each morphism is 
> from one object
> to another (not necessarily different) object.  Where the destination 
> of one morphism
> is the source of a second, their composition is defined; composition is 
> associative where
> it is defined.  Each object has an identity morphism, which connects it 
> to itself; this
> is an identity when composed with morphisms coming in and with 
> morphisms going
> out.
> ________________________________________________________________________
> Check Out the new free AIM(R) Mail -- 2 GB of storage and 
> industry-leading spam and email virus protection.
>