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.<br>

<br>

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.<br>

<br>

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.<br>

<br>

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.<br>

<br><div><span class="gmail_quote">On 11/29/06, <b class="gmail_sendername"><a href="mailto:franktaw@netscape.net">franktaw@netscape.net</a></b> <<a href="mailto:franktaw@netscape.net">franktaw@netscape.net</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;">Thanks, Christian.<br><br>I think we need to look at one more table:  the number of connected

<br>categories with n morphisms and k objects.  This starts:<br><br>  1<br>  2<br>  7 1<br> 35 6<br>228 28 2<br><br>(Row n has length ceiling(n/2).)<br><br>The table of the number of categories that I started with is a two-

<br>dimensional Euler transform of this table.<br><br>The downward-sloping diagonal sums of this table are 1,3,15,???.<br>Shifting this left and taking the Euler transform gives the limiting<br>values Christian is referring to; starting with b(0):

<br><br>1,3,21,???<br><br>For the table above, a(2n-1,n) has a purely algebraic or graph-<br>theoretic interpretation.  It is the number of connected<br>anti-transitive relations on n objects (meaning that if a R b and<br>

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.

<br><br>Franklin T. Adams-Watters<br><br><br>-----Original Message-----<br>From: <a href="mailto:bowerc@usa.net">bowerc@usa.net</a><br><br>I have one more row to add<br><br>------ Original Message ------<br>Received: Wed, 22 Nov 2006 01:21:01 PM PST

<br><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>228 77 20 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>329<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).<br><br>

While the 329 is eerily close to A001776's 330, EULER(A058129) is a<br>lower limit for this sequence and we have 2982 vs 2345 for #6 there.<br>>  The<br>> inverse Euler<br>> transform,<br>><br>> 1,2,8,41<br>

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?

<br>><br>> Franklin T. Adams-Watters<br>><br><br>Christian<br><br>PS<br><br>I don't know if it will be feasible to collect enough data to do<br>this, but the columns of the triangle converge and that convergence<br>

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.

<br><br></blockquote></div><br>