Endofunctions by indegree

[franktaw at netscape.net]

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.