Endofunctions by indegree

[franktaw at netscape.net]

Mostly to Jonathon,

Yes, that is exactly what I mean - although I think you have a typo: I 
think E should be 1,1,1,0, not 1,1,2,0.  To make a partition out of 
this, use these as the exponents: [0^1,1^1,2^1,3^0]; simplifying and 
discarding the zeros gives [2,1].  Likewise A:0,3,0,0 becomes the 
partition [1^3] (which is another way of saying [1,1,1]).

Note that my second table, with the partitions, is really the most 
fundamental; the other two can obtained by summing suitable values from 
the corresponding row of that table.

I think there's at least one problem with the Goedel table (A125024): 
1500 = 2^2 * 3^1 * 5^3 is the endofunction 2,1,3.  But the equivalent 
3,2,1 has Goedel value 360.  So, instead of ..., 540, 1500, ..., it 
should be ..., 360, 540, ....  I'm guessing that you did this table by 
hand.  I'll try to find time to program it.

Franklin T. Adams-Watters


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

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.