Partial endofunctions (was Re: categories)

[Jonathan Post]

Christian G. Bower,

That's an amazing theorem that you described.  I'm wrestling for a proof.

Bower's Theorem: The number of nonisomorphic partial functions a(n) on n
indistinguishable objects is the Euler transform of the sum of A002861 (the
number of connected functions on n unlabeled points, or rings and branches
with n edges), and A000081 (the number of rooted trees with n nodes (or
connected functions with a fixed point).

Related to this, A001372  (the number of mappings, or mapping patterns, from
n points to themselves, the number of endofunctions on n points) is the
Euler transform of A002861 (the number of connected functions on n unlabeled
points, or rings and branches with n edges).

This ties together a lot of important sequences.  Is there a published
proof, or is this new to you?  In either case, it certainly deserves to be
in OEIS, to begin with!

Thanks for a great Hanukkah/Christmas present, Christian!

-- Jonathan Vos Post

On 12/24/06, Christian G. Bower <bowerc at usa.net> wrote:
>
> 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 ------
> Received: Sun, 24 Dec 2006 12:36:38 AM PST
> 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
> >
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061224/5697ed9b/attachment-0002.htm>