Endofunctions by indegree

[franktaw at netscape.net]

I have now extended these myself.

The table by maximum indegree starts:
1
2 1
3 3 1
5 10 3 1
7 24 12 3 1
11 64 39 12 3 1
15 149 122 41 12 3 1
22 366 368 138 41 12 3 1
30 857 1092 439 140 41 12 3 1

The column limit, starting 1,3,12,41,140, is not in the OEIS.

The table by indegree partition, in Mathematica order, starts:
1
1
1 2
1 3 3
1 3 3 7 5
1 3 4 8 10 14 7
1 3 4 8 3 19 17 6 32 26 11
1 3 4 8 4 19 18 11 14 63 34 29 75 45 15
1 3 4 8 4 19 18 3 20 14 64 37 14 39 85 168 62 15 109 167 75 22
1 3 4 8 4 19 18 4 20 14 64 38 11 26 71 86 175 70 7 90 103 43 346 394 
109 84 324 329 120 30

Note that in this order, the rows approach a limit.  This limit is 
actually a function on partitions, and it is not in the OEIS.

The table by number of elements in the image starts:
1
1 2
1 3 3
1 6 7 5
1 7 18 14 7
1 10 33 49 26 11
1 11 52 110 109 45 15
1 14 75 221 314 229 75 22
1 15 105 372 746 788 438 120 30

This agrees with the values Christian posted.

I have also calculated a couple more tables.  The first is the 
partition representing the sizes of the connected components.  This 
starts, in Mathematica order:
1
2 1
4 2 1
9 4 3 2 1
20 9 8 4 3 2 1
51 20 18 9 10 8 4 4 3 2 1
125 51 40 20 36 18 9 10 12 8 4 4 3 2 1
329 125 102 51 80 40 20 45 36 27 18 9 20 10 12 8 4 5 4 3 2 1
862 329 250 125 204 102 51 180 80 60 40 20 45 72 36 27 18 9 20 20 10 16 
12 8 4 5 4 3 2 1
The first column here is A002861, and so is the second (offset).

Next is the loop sizes.  Each endofunction contains exactly one loop in 
each component, but the loop size may be smaller than the component 
size.  In this case, each row contains all non-empty partitions up to 
size n; this table is again in Mathematica order:
1;
1, 1 1;
2, 1 1, 1 1 1;
4, 3 3, 1 2 1, 1 1 1 1 1;
9, 6 6, 3 6 3, 1 2 1 2 1, 1 1 1 1 1 1 1;
20, 16 16, 9 15 7, 4 6 4 7 3, 1 2 2 2 2 2 1, 1 1 1 1 1 1 1 1 1 1 1;
48, 37 37, 23 41 18, 11 18 9 18 7, 4 7 7 7 7 7 3 1, 2 2 2 1 3 2 1 2 2 1 
1, 1 1 1 1 1 1 1 1 1 1 1 1 1 1;
115, 96 96, 62 106 44, 35 51 28 53 19, 14 21 21 21 19 19 7, 5 7 8 8 4 
11 7 4 8 7 3, 1, 2 2 2 2 3 2 2 2 3 2 2 2 2, 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1;
286, 239 239, 169 284 117, 97 144 71 142 46, 46 67 63 63 58 56 19, 18 
24 24 24 12 36 22 10 22 19 7, 5 8 8 8 8 12 8 7 8 12 7 7 8 7 3, 1 2 2 2 
2 3 2 1 3 2 3 2 2 2 3 3 2 1 2 2 2 1, 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1;
The first column is of course A000081, the number of rooted trees.  
Several other columns are also in the EOIS.  The final part of each row 
is always all 1's, the permutation with the specified cycle structure.

Franklin T. Adams-Watters


-----Original Message-----
From: franktaw at netscape.net

Given a finite set S with n elements, endofunctions on S are there 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: 
... 
 
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): 
...
 
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: 
... 

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