Partial endofunctions (was Re: categories)

[Christian G. Bower]

Note: I see as I wrote this that ftaw covered some of the same material,
but I'll send this anyway to cover the references.

------ Original Message ------
From: "Jonathan Post" <jvospost3 at gmail.com>
To: "Christian G. Bower" <bowerc at usa.net>Cc: seqfan <seqfan at ext.jussieu.fr>,
jvospost2 at yahoo.com
Subject: Re: Partial endofunctions (was Re: categories)

> 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!

As far as published proofs go, I've never seen anything published about
partial endofunctions, but I have read plenty about the normal kind of
endofunctions and in particular the methods used to do the counting.

My main source is the Bergeron/Labelle/Leroux reference in A001372
which explains the method in detail.

The idea here is that a connected endofunction is a directed cycle of
rooted trees. Hence we have A002861 = CIK(A000081).

CIK defined in my article at
http://www.research.att.com/~njas/sequences/transforms2.html

Endofunctions are sets of connected endofunctions (described in BLL as
permutations of rooted trees) hence A001372 = EULER(A002861)

A partial endofunction essentially has two kinds of fixed points. The
normal kind f(x)=x and the other kind of f(x) is undefined.
Combinatorially they are the same.

The connected strictly partial endofunctions are combinatorially the
same as rooted trees.

Thus to get connected (not strictly) partial endofuntions we take
A002861 + A000081
and EULER(A002861+A000081) for all partial endofuntions

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