Categories

[Jonathan Post]

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





On 12/23/06, Dean Hickerson <dean at math.ucdavis.edu> wrote:
>
> Mostly to Jonathan Post:
>
> > Trapped on a holiday morning with no PC or even hand calculator about, I
> > started enumerating by hand the nonisomorphic partial endofunctions on n
> > indistinguishable objects.
>
> I haven't seen the word "endofunction" before.  Do you just mean a
> function
> from some subset of the set of n elements into the same set of n elements?
>
> > That is, charted by digraphs with outdegree 0 or 2 at each vertex.
>
> Do you mean "outdegree 0 or 1"?
>
> > There are 5 PFGs on 2 points: 0 arcs and 0, 1, or 2 loops on two
> > disconnected vertices, and 1->2 where 2 either has no out-link or a
> loop.
>
> If I understand correctly what you're counting, I find 6 of them; with
> 1->2, 2 can either have no out-link, or a loop, or an arc back to 1.
>
> Am I confused about what you're counting, or did you miss one?
>
> Dean Hickerson
> dean at math.ucdavis.edu
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061224/bc0bb74a/attachment-0003.htm>