Categories

[Christian G. Bower]

------ Original Message ------
From: "Jonathan Post" <jvospost3 at gmail.com>
To: "franktaw at netscape.net" <franktaw at netscape.net>Cc: bowerc at usa.net,
seqfan at ext.jussieu.fr, jvospost2 at yahoo.com
Subject: Re: Categories

> a(n) = 2*A000055(n) - A000081(n/2) = (2* Number of trees with n unlabeled
> nodes) - Number of rooted trees with n/2 nodes (or connected functions with
> a fixed point)
> 
> where a(n) is downwards sloping diagonal sums of main category table, or
> what?

Actually it's the "corner" values from this table

>   *1*
>   2
>   7 *1*
>  35 6
> 228 28 *2*
> 2237 159 11
> 31559 ?   ? *3*

The downward sloping sums were an aide in calculating the convergent
sequence of the columns

The interpretation of these corners comes from the fact we have a
saturated category. It has 2n-1 elements, n of which are object
identities. It's connected, so it has a minimum of n-1 "crossover"
morphisms, it also has a maximum of n-1 cm's since there are only
n-1 elements left. Any connected graph with n points and n-1 edges is
a tree. The associativity of categories states that if we have an
a-b morphism (an edge on the graph) and a b-c we must have an a-c.
But if we have all 3, it's no longer a tree, hence we never have the
a-b and the b-c, hence each point has all edges either pointing in or
pointing out, hence the biparite graph analogy, hence a little
combinatorial magic.

...
> Funny how Category Theory folks tend to be addicted to theory for its > own
> sake, and less willing to "get their hands dirty" with anything as old
> fashioned as enumeration.  OEIS helps us focus here, by demanding the
> integer sequences!
> 

I try to stay out of philosophical stuff here, but sometimes it's too
hard to resist. I figure I'm guilty of spending too much time counting
stuff and not taking the theory in. Most of the world would not give a
hoot about either, so I'm glad there are folk spending time on what I
would not give any time to.

Still, I find it jarring any time I read a math paper and they write
about several things that can be represented as sequences, yet all they
give is a mathematical description, rarely do they cite the OEIS
reference or even give me the first n terms leaving me to calculate them
myself and hope I didn't make a mistake. If I wrote a paper, I'd
include that stuff, not just because I'm an OEIS nerd, but also because
I would want people to be able to find my paper who didn't know they
were looking for it.

Just a little more self indulgence here with my list of semigroup pipe
dreams. After doing sequences on semigroups
http://www.research.att.com/~njas/sequences/A027851
and monoids
http://www.research.att.com/~njas/sequences/A058129
I knew categories was one of the next logical steps, but I held off
because I knew it would be difficult. Perhaps I can spur someone else's
interest in related problems that may prove even more difficult.

There's transformation semigroups, the semigroup version of permutation
groups
http://www.research.att.com/~njas/sequences/A000638
I've seen TSs written about, but no attempts to enumerate them.
(Note, a TS is any set of endofunctions closed under composition)
There TS's close cousins which could be called:
transformation monoids
relation semigroups
relation monoids
(Composition of relations is such that (a,c) is in R1(R2) iff there
is b such that (a,b) in R1 and (b,c) in R2)
Then there are the generalizations of categories to semigroups and
groupoids. Note I mean the groupoid that is a set and closed operation
http://www.research.att.com/~njas/sequences/A001329
Not the group like category groupoid which might also be interesting
to count and not too difficult; oh terminology.
Anyway, with the semigroup and groupoid categories, there comes the
issue of treating objects and morphims. The ordinary (monoid like)
categories avoid this problem by having object identities among the
morphisms that can be associatied with the objects themselves. Without
that restriction, it's possible to have objects untouched by any
morphism or two structures with identical (or isomorphic) multiplication
tables, but not isomorphic when you take the objects into account.
Basically many of the same counting problems one has with multigraphs
(and probably the same solutions too.)