Endofunctions by indegree

[Jonathan Post]

Dear Frank,

I have a couple of hunded handwritten and hand-drawn pages of digraphs of
endofunctions, and am waiting for my son to get back from his ski trip to do
another rewrite of our paper on them.

For each endofunction through n=7 nodes, I have a drawing, and a table
enumerating oh many cycles there are of each size through cycle length n.

By inspection I can count off the table of the number of nodes of given
number of indegrees.

Before I get too deeply into that task, and before I break for dinner (my
wife is calling me), let me be sure we're on the same page.

I can describe each (up to isomorphism) endofunction on n nodes by picking a
specific labeling from [n] = {1,2,...,n}, count indegrees of each node, and
then throw away the labels.

n=0, the null graph can formally be said to have one node with indegree
zero.

n=1, (1)->(1) has 0 nodes of indegree 0 and 1 of indegree 1.

n=2, there are 3 endofunctions:

(1,2)->(1,2) has 0 nodes of indegree 0 and 2 of indegree 1.

(1,2)->(2,2) has 1 node of indegree 0 and 1 of indegree 2.

(1,2)->(2,1) has 0 nodes of indegree 0 and 2 of indegree 1.

n=3, there are 7 endofunctions:
My notes label them A-G
The table of the number of nodes of indegree k for k = 0,1,2,3 is:
A:0,3,0,0
B:0,3,0,0
C:0,3,0,0
D:1,1,1,0
E:1,1,2,0
F:2,0,0,1
G:1,1,1,0

See my seq of the Goedel number of endofunctions (I spell it that way,
lacking an umlaut).

Back to you after dinner.

Best,

Jonathan


On 12/28/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
>
> Given a finite set S with n elements, how many functions are there from
> S -> S (endofunctions on S) such that the maximum number elements
> mapped to any one element is k?  In graph terms, how many functional
> digraphs are there with n nodes, and maximum indegree k?
>
> If we regard the elements of S (aka the points of the graph) as
> distinguishable (labeled), the answer is
> http://www.research.att.com/~njas/sequences/A019575.  However, if the
> points are not labeled, the table starts:
> 1
> 2  1
> 3  3  1
> 5 10  3  1
> 7 24 12  3  1
>
> This is not in the OEIS.  Obviously, the first column is the partition
> numbers, A000041.  The columns approach a limit (starting 1,3,12), but
> there is not enough data here to do any analysis on that.
>
> Similarly, we can look at the partition formed by the indegrees of all
> nodes.  Again, the sequence for labeled nodes is in the OEIS; it is
> http://www.research.att.com/~njas/sequences/A049009 (in A&S order).
> For unlabeled nodes, the sequence is again not present; it starts (with
> n=0 first):
> 1
> 1
> 1 2
> 1 3 3
> 1 3 3 7 5
> 1 3 4 8 10 14 7
>
> (in either A&S or Mma order, as these diverge first at n = 6).
>
> Third, one can look at how many elements are in the image of the
> function.  A pattern is developing here; the labeled version is in the
> OEIS: A090657 or A101817 (with different offsets); but the unlabeled
> version is not; it starts:
> 1
> 1 2
> 1 3  3
> 1 6  7  5
> 1 7 18 14 7
>
> Row sums for all three tables are in
> http://www.research.att.com/~njas/sequences/A001372.
>
> These are hand-calculated; I have done some cross-checks, so I have a
> fair degree of confidence in them, but not 100%.
>
> I would appreciate it if someone could verify these and - even better -
> extend them.  I then plan to submit them.
>
> Franklin T. Adams-Watters
>
> ________________________________________________________________________
> Check Out the new free AIM(R) Mail -- 2 GB of storage and
> industry-leading spam and email virus protection.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061228/c30f35ac/attachment-0002.htm>