Partial endofunctions (was Re: categories)

[Christian G. Bower]

I get:

1 2 6 16 45 121 338 929 2598 7261 20453...

It's just EULER(A002861+A000081)

I remember thinking about this problem years ago.

I guess I never got around to sending it in.

------ Original Message ------
From: "Jonathan Post" <jvospost3 at gmail.com>
To: "Dean Hickerson" <dean at math.ucdavis.edu>Cc: seqfan at ext.jussieu.fr,
jvospost2 at yahoo.com
Subject: Re: Categories

> You're right, Dean Hickerson.  I missed the obvious 2-cycle  (1,2)->(2,1).
I
> did make the typo, and meant outdegree 0 or 1.
> 
> When outdegree is always 1, we have the functional graphs, same as
> endofunctions. As in A125024. When some points have no function from them
> defined, neither being in a cycle of length >1 nor with a loop (1-cycle),
> that is the partial functional graphs I was counting.
> 
>  If one writes an endofunction over n points (finite n) and numbers the
> points 1 through n, then each labeled sagittal graph (directed graph,
> "sagittal" = "with arrows") of a function from (1,2,3,..., z) to (a, b, c,
> .., z) with a, b, c, ..., z elements of (1,2,3,..., z).
> 
> The point is that the enumeration is up to isomorphism, so that 1-> is the
> same as 2->1. In the 2-cycle you pointed out, 1<=>2 is isomorphic to 2<=>1,
> of course.  We label for notation, and then permute the labels as needed.
> 
> The corrected count for n = 0,1,2,3,4,5 is now:
> a(n) = 1, 2, 6, 16, 45, 121?
> 
> That starts the same through n=4, but is off by 1 for n=5 from A055544
Total
> number of nodes in all rooted trees with n nodes, where A055544(5) = 120.
If
> I missed one for n=5 (seems more likely now with the omission that you
> caught) then there must be an obvious isomorphism between these one-to-one
> partial function on n points and A055544.  Is that the Joyal isomorphism?
> 
> Munn [1957] gave a notation that generalized cycle notation for
> permutations.  Lipscomb [1986] gave a path notation, motivated by digraph
> representations of charts (partial one-one transformations).
> 
> Konieczny and Lipscomb, Math. Japonica 48, No.3(1998)367-376 give a lovely
> enumeration in "Centralizers in the semigroup of partial transformations"
> and I was trying to get an integer sequence out of their approach.  The
> semigroup is the natural one by composition of transformations on the the
> partial functions.
> 
> Since A055544(6) = 336, are there 336 nonisomorphic partial functions on 6
> points?
> 
> Thanks for catching my goof.
> 
> Must wrap some presents now...
> 
> Best of the holiday season to you & yours,
> 
> -- Jonathan Vos Post
>