A060281 Triangle T(n,k) giving number of labeled mappings (or functional digraphs) from n points to themselves (endofunctions) with k cycles, k=1..n. My handwritten notes give the equivalent for unlabeled mappings, which I don't see in OEIS.

<br><br>My arbitrary designations of n+2 are:<br><br>A_2: (1,2)->(1,2) has 0 nodes of indegree 0 and 2 of indegree 1.<br><br>B_2: (1,2)->(2,2) has 1 node of indegree 0 and 1 of indegree 2.

<br><br>C_2: (1,2)->(2,1) has 0 nodes of indegree 0 and 2 of indegree 1.<br><br>One typo corrected from before:<br><br>n=3, there are 7 endofunctions:<br>My notes label them A-G<br>The table of the number of nodes of indegree k for k = 0,1,2,3 is:

<br>A_3 (1,2,3)->(1,2,3) :0,3,0,0<br>

B_3 (1,2,3)->(2,3,1) :0,3,0,0<br>C_3 (1,2,3)->(1,3,2) :0,3,0,0<br>D_3 (1,2,3)->(1,2,1) :1,1,1,0<br>E_3 (1,2,3)->(1,3,1) :0,1,2,0<br>F_3 (1,2,3)->(3,3,3) :2,0,0,1<br>G_3 (1,2,3)->(2,1,1) :1,1,1,0<br>-------------

<br>7:                           4,12,4,1 column sums<br><br>We can count off how many rows correspond to any given partition of n.<br><br>n=4 has 19 endofunctions.  7 of these are just the direct sum of a loop and one of the 7 3-endofunctions. Call these a_4, B_4, ..., G_4. There are 11 more, which in my notes were arbitrarily designated 

<br>H_4 (1,2,3,4)->(2,3,4,2) ,<br>I_4 = B_2 + B_2 <br>J_4 (1,2,3,4)->(2,3,4,4), <br>K_4 (1,2,3,4)->(3,3,4,4), <br>L_4 (1,2,3,4)_>(4,3,4,4), <br>M_4 =b_2 + C_2, <br>N_4 = B_2 x B_2, <br>O_4 (1,2,3,4)->(2,3, 4,3), 

<br>P_4 = B_2 x C_2, <br>Q_4 (1,2,3,4)-(3,3,4,3)<br>R_4 = C_2 + C_2, <br>S_4 (1,2,3,4)->(2,3,4,1)<br>where the "x" means categorical product, and "+" means direct sum.<br><br>We can classify these by cycle index, the number of cycles of length 1,2,...,n

<br>A_4: 4,0,0,0<br>B_4: 1,0,1,0<br>C_4: 2,1,0,0<br>D_4: 3,0,0,0<br>E_4: 2,0,0,0<br>F_4: 2,0,0,0<br>G_4: 1,1,0,0<br>H_4: 0,0,1,0<br>I_4: 2,0,0,0<br>J_4: 1,0,0,0<br>K_4: 1,0,0,0<br>L_4: 1,0,0,0<br>M_4: 1,1,0,0<br>N_4: 1,0,0,0

<br>O_4: 0,1,0,0<br>P_4: 0,1,0,0<br>Q_4: 0,1,0,0<br>R_4: 0,2,0,0<br>S_4: 0,0,0,1<br>------------------<br>19    22,8,2,1  column sums<br><br>6 of these are loop-free, 1 is arc-free, 12 are mixed<br><br>The ones "prime" in my analysis (neither the direct sum nor dierect product of prime endofunctions) are H, J, K, L, O, Q, S.

Do you want more such tables, and my tables of i-degrees and size of images? I like your suggested tables, and can painstakingly verify or correct if you'd like.  Do you see why I think it best to focus on the primes, as thers can have their caharacteristics quickly generated from their sum or product of "prime" endofunctions? The Goedel numbering gives a canonical representation of [n]->[n].

<br><br>-- Jonathan Vos Post<br><br><br><div><span class="gmail_quote">On 12/28/06, <b class="gmail_sendername">Jonathan Post</b> <<a href="mailto:jvospost3@gmail.com">jvospost3@gmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

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.

<br><br>n=1, (1)->(1) has 0 nodes of indegree 0 and 1 of indegree 1.<br><br>n=2, there are 3 endofunctions:<br><br>(1,2)->(1,2) has 0 nodes of indegree 0 and 2 of indegree 1.<br><br>(1,2)->(2,2) has 1 node of indegree 0 and 1 of indegree 2.

<br><br>(1,2)->(2,1) has 0 nodes of indegree 0 and 2 of indegree 1.<br><br>n=3, there are 7 endofunctions:<br>My notes label them A-G<br>The table of the number of nodes of indegree k for k = 0,1,2,3 is:<br>A:0,3,0,0<br>

B:0,3,0,0<br>C:0,3,0,0<br>D:1,1,1,0<br>E:1,1,2,0<br>F:2,0,0,1<br>G:1,1,1,0<br><br>See my seq of the Goedel number of endofunctions (I spell it that way, lacking an umlaut).<br><br>Back to you after dinner.<br><br>Best,<br>

<span class="sg">

<br>Jonathan</span><div><span class="e" id="q_10fcc222d726eed7_2"><br><br><br><div><span class="gmail_quote">On 12/28/06, <b class="gmail_sendername"><a href="mailto:franktaw@netscape.net" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

franktaw@netscape.net</a></b> <<a href="mailto:franktaw@netscape.net" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">franktaw@netscape.net

</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Given a finite set S with n elements, how many functions are there from

<br>S -> S (endofunctions on S) such that the maximum number elements<br>mapped to any one element is k?  In graph terms, how many functional<br>digraphs are there with n nodes, and maximum indegree k?<br><br>If we regard the elements of S (aka the points of the graph) as

<br>distinguishable (labeled), the answer is<br><a href="http://www.research.att.com/%7Enjas/sequences/A019575" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.research.att.com/~njas/sequences/A019575

</a>.  However, if the<br>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.

<br><br>Similarly, we can look at the partition formed by the indegrees of all<br>nodes.  Again, the sequence for labeled nodes is in the OEIS; it is<br><a href="http://www.research.att.com/%7Enjas/sequences/A049009" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

http://www.research.att.com/~njas/sequences/A049009

</a> (in A&S order).<br>For unlabeled nodes, the sequence is again not present; it starts (with<br>n=0 first):<br>1<br>1<br>1 2<br>1 3 3<br>1 3 3 7 5<br>1 3 4 8 10 14 7<br><br>(in either A&S or Mma order, as these diverge first at n = 6).

<br><br>Third, one can look at how many elements are in the image of the<br>function.  A pattern is developing here; the labeled version is in the<br>OEIS: A090657 or A101817 (with different offsets); but the unlabeled<br>

version is not; it starts:<br>1<br>1 2<br>1 3  3<br>1 6  7  5<br>1 7 18 14 7<br><br>Row sums for all three tables are in<br><a href="http://www.research.att.com/%7Enjas/sequences/A001372" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

http://www.research.att.com/~njas/sequences/A001372

</a>. 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.

<br><br></blockquote></div><br>

</span></div></blockquote></div><br>