Endofunctions by indegree

[Christian G. Bower]

------ Original Message ------
From: franktaw at netscape.net
To: seqfan at ext.jussieu.fr
Subject: Endofunctions by indegree

> 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?
> 
...
> 
> 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
> 

For a quick answer to your 3rd question

1 
1 0 
2 1 0 
3 3 1 0 
5 7 6 1 0 
7 14 18 7 1 0 
11 26 49 33 10 1 0 
15 45 109 110 52 11 1 0 
22 75 229 314 221 75 14 1 0 
30 120 438 788 746 372 105 15 1 0 
42 187 806 1797 2222 1508 601 136 18 1 0 
56 284 1404 3806 5888 5208 2763 888 174 19 1 0 
77 423 2378 7605 14368 15960 10914 4662 1277 216 22 1 0 
...
Column 0 http://www.research.att.com/~njas/sequences/A000041
Column 1 http://www.research.att.com/~njas/sequences/A014153
n-1 diagonal http://www.research.att.com/~njas/sequences/A042964

This is in reverse order because I counted the leaves of the digraph
(those with indegree 0) so it's effectively by those the number not
in the range. Note that the left most column is column 0.

What I did here was to follow the formula for endofunctions:
EULER(CIK(Rooted trees)) using the triangle of rooted trees by their
leaves as the inside sequence
http://www.research.att.com/~njas/sequences/A055277

I had to modify the table so that the 1-node rooted tree did not have a
leaf (as it does not when it represents an endofunction.)

Your first question would amount to the same sort of thing using trees
whose nodes have at most k children. Some care will have to be taken for
nodes that are part of a cycle of length more than 1 as they have an
additional input from the cycle.

The second looks like a lot of book keeping.

I can look at these more after the weekend.

Christian

> Row sums for all three tables are in 
> http://www.research.att.com/~njas/sequences/A001372.
...
> 
> Franklin T. Adams-Watters
>