Christian G. Bower,<br>

<br>

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

<br>

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

<br>

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

<br>

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

<br>

Thanks for a great Hanukkah/Christmas present, Christian!<br>

<br>

-- Jonathan Vos Post<br><br><div><span class="gmail_quote">On 12/24/06, <b class="gmail_sendername">Christian G. Bower</b> <<a href="mailto:bowerc@usa.net">bowerc@usa.net</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

I get:<br><br>1 2 6 16 45 121 338 929 2598 7261 20453...<br><br>It's just EULER(A002861+A000081)<br><br>I remember thinking about this problem years ago.<br><br>I guess I never got around to sending it in.<br><br>------ Original Message ------

<br>Received: Sun, 24 Dec 2006 12:36:38 AM PST<br>From: "Jonathan Post" <<a href="mailto:jvospost3@gmail.com">jvospost3@gmail.com</a>><br>To: "Dean Hickerson" <<a href="mailto:dean@math.ucdavis.edu">

dean@math.ucdavis.edu</a>>Cc: <a href="mailto:seqfan@ext.jussieu.fr">seqfan@ext.jussieu.fr</a>, <a href="mailto:jvospost2@yahoo.com">jvospost2@yahoo.com</a> Subject: Re: Categories > You're right, Dean Hickerson.  I missed the obvious 2-cycle  (1,2)->(2,1).

<br>I<br>> did make the typo, and meant outdegree 0 or 1.<br>><br>> When outdegree is always 1, we have the functional graphs, same as<br>> endofunctions. As in A125024. When some points have no function from them

<br>> defined, neither being in a cycle of length >1 nor with a loop (1-cycle),<br>> that is the partial functional graphs I was counting.<br>><br>>  If one writes an endofunction over n points (finite n) and numbers the

<br>> points 1 through n, then each labeled sagittal graph (directed graph,<br>> "sagittal" = "with arrows") of a function from (1,2,3,..., z) to (a, b, c,<br>> .., 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.

<br>><br>> The corrected count for n = 0,1,2,3,4,5 is now:<br>> a(n) = 1, 2, 6, 16, 45, 121?<br>><br>> That starts the same through n=4, but is off by 1 for n=5 from A055544<br>Total<br>> 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).

<br>><br>> Konieczny and Lipscomb, Math. Japonica 48, No.3(1998)367-376 give a lovely<br>> enumeration in "Centralizers in the semigroup of partial transformations"<br>> and I was trying to get an integer sequence out of their approach.  The

<br>> semigroup is the natural one by composition of transformations on the the<br>> partial functions.<br>><br>> Since A055544(6) = 336, are there 336 nonisomorphic partial functions on 6<br>> points?<br>>

<br>> Thanks for catching my goof.<br>><br>> Must wrap some presents now...<br>><br>> Best of the holiday season to you & yours,<br>><br>> -- Jonathan Vos Post<br>><br><br><br><br></blockquote>

</div><br>