Partial endofunctions (was Re: categories)

[franktaw at netscape.net]

It's simple enough.  Start with any element, and keep applying the 
(partial) function if you can.  Eventually, one of two things happens:

1) You get a loop back to one of the elements you already had, or
2) You get to an element for which the function is not defined.

Now, look at everything that flows into the same limit: in case 1, you 
have a connected function on some number of points, and in case 2, you 
have a rooted tree.  The entire function is just some number of 
independent structures of one or the other of these types - and that is 
what the Euler transform counts.

I remember thinking about this some time ago, and I actually thought I 
had submitted the sequence; but I can find no evidence that I did so.

Franklin T. Adams-Watters


-----Original Message-----
From: jvospost3 at gmail.com

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







________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.