Categories

[Jonathan Post]

The issue of "connected" in the underlying functional graph, as a subset of
the set of all digraphs, is further revealed by the distinction (definitions
at MathWorld) of Weakly Conncted versus Strongly Conncted Digraphs.

Every functional digraph is the disjoint union of connected digraphs.
That's why there is a recursion in the enumeration of F(n) = functional
graphs on n points. F(n) is equal or greater to the number of functional
graphs on n-1 points, unioned with an isolated point looping to itself, plus
the number of functional graphs on n-2 points unioned with any of the 3
functional graphs on 3 points, ..., throwing out any double or multiple
counts by equivalence class on isomorphisms of the unlabelled digraphs.

Note that MathWorld's correct definition of functional graph, and its
Mathematica, is identical to what I'd called endofunctions in earlier
posting of this thread.  Hence the enumeration problem that I solved for
"prime" endofunctions is identical to a subset of your category enumeration
problem, relating to the number of categories that are not unions nor
categorical products of smaller categories.

However, when I referred to 2-categories before, I should more correctly
have said Bicategories, the difference being based on whether associativity
is strict or up to 2-isomorphism.  Your enumeration of categories is more
formally explained in terms of Cat, the category of categories and functors,
but this is not the right venue for me to go into excruciating details.

On 11/29/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
>
> Thanks, Christian.
>
> I think we need to look at one more table:  the number of connected
> categories with n morphisms and k objects.  This starts:
>
>   1
>   2
>   7 1
> 35 6
> 228 28 2
>
> (Row n has length ceiling(n/2).)
>
> The table of the number of categories that I started with is a two-
> dimensional Euler transform of this table.
>
> The downward-sloping diagonal sums of this table are 1,3,15,???.
> Shifting this left and taking the Euler transform gives the limiting
> values Christian is referring to; starting with b(0):
>
> 1,3,21,???
>
> For the table above, a(2n-1,n) has a purely algebraic or graph-
> theoretic interpretation.  It is the number of connected
> anti-transitive relations on n objects (meaning that if a R b and
> b R c, then NOT (a R c)); equivalently, the number of bipartite
> oriented trees, where each edge origin is in the same part.
>
> If I haven't made any mistakes, this sequence starts:
>
> 1,1,2,3,6,10
>
> This is not enough data to determine whether it is in the OEIS.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: bowerc at usa.net
>
> I have one more row to add
>
> ------ Original Message ------
> Received: Wed, 22 Nov 2006 01:21:01 PM PST
>
> > 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
> >
> 228 77 20 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
> 329
> >
> > the number of categories with n morphisms.  This is probably not in
> the
> > OEIS (only
> > A001776 is possible - other matches become less than A058129).
>
> While the 329 is eerily close to A001776's 330, EULER(A058129) is a
> lower limit for this sequence and we have 2982 vs 2345 for #6 there.
> >  The
> > inverse Euler
> > transform,
> >
> > 1,2,8,41
> 258
> >
> > is the number of connected categories with n morphisms; this is
> > likewise probably not
> > in the OEIS (only A052447 is possible).
> No longer possible
> >
> > Can somebody generate more data?
> >
> > Franklin T. Adams-Watters
> >
>
> Christian
>
> PS
>
> I don't know if it will be feasible to collect enough data to do
> this, but the columns of the triangle converge and that convergence
> would make an interesting sequence in and of itself.
>
> ________________________________________________________________________
> Check Out the new free AIM(R) Mail -- 2 GB of storage and
> industry-leading spam and email virus protection.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061129/3cb88b67/attachment-0003.htm>