<p>Mean Cycle Length and Mean Number of Predecessors<br>

<b><br>

</b>We know asymptotically [Flajolet & Odlyzko, 19xx]; the

mean cycle length and mean number of predecessors of points in

constrained random functional graphs. But Prime endofunctions are not

random.</p>

<p>The [see handwritten drawings and tables on yellow pad] calculated

mean cycle length of prime endomorphisms on n vertices, 1<n<8. <br>

 <br>

mu(2) = 3/2 = 1.5 <br>

mu(3) = 9/4 = 2.25 <br>

mu(4) = 15/7 = 2.143 <br>

mu(5) = 40/21 = 1.905 <br>

mu(6) = 55/23 = 2.391 <br>

mu(7) = 110/42 = 2.619 <br>

 <br>

The [see other handwritten drawings and tables on yellow pad]

calculated mean number of predecessors over all vertices of prime

endomorphisms on n vertices, 1<n<8. <br>

</p>

<p>One can also calculate the "average tail length" of the direct graphs of prime endofunctions.<br>

<br>

cf: Bernhard Gittenbeger, "On the number of Predecessors in Constrained Random Mappings"<br>

<br>

Define omega(F(n)) on a functional graph F(n) with n points, as the

average number of preimages (or predecessors) of a vertex in F(n).  We

know what this is, asymptotically, on random functional graphs.  But

prime endofunctions are not random.  We easily computer pi(n) =

mean(omega(PrimeEndofunction(n))).<br>

<br>

For n=2<br>

B_2 (1,2)->(2,2): 1 has 0 preimages, 2 has 2, total = 2<br>

C_2 (1,2)->(2,1): 1 has 2 primages, 2 has 2 preimages, total = 4<br>

so Omega(2) = ((2+4)/2) = 3.<br>

<br>

n = 3<br>

(1,2,3)->(2,3,3) preimages = 0,1,2 total = 4<br>

(1,2,3)->(2,2,2) preimages 0,0,0 total = 3<br>

(1,2,3)->(2,3,2) preeimages 0,2,3 total = 5<br>

(1,2,3)->(2,3,1) preimages 3,3,3 total = 9<br>

so Omega(3) = ((4+3+5+9)/6) = 3.5<br>

<br>

Coutier & Holden, p.2 rephrases:<br>

"... x is a terminal node if f^(-1)=null set.  A node is an image node if it is not a terminal node..." <br>

</p>

<p><br>

after a bit of computing...<br>

</p>

<p>pi(2) = 6/2 = 3 <br>

pi(3) = 21/6 = 3.5 <br>

pi(4) = 63/7 = 9 <br>

pi(5) = 234/21 = 11.1429 <br>

pi(6) = 396/23 = 17.217391 <br>

pi(7) = 933/42 = 22.214285</p>

These sequences of numerators and denominators are not "frac" seqs yet in OEIS.<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;">

Yes, that's the most substantial correction to A125024, there are a few

lesser ones too, which I made by hand within a week of submission, and

either never sent to njas or are in the queue. Thanks. Apologies to Girard for over 1 gmail per hour, here.

<div><span class="e" id="q_10fcc6e447d58a53_1"><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;">Mostly to Jonathon,<br><br>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]).

<br><br>Note that my second table, with the partitions, is really the most<br>fundamental; the other two can obtained by summing suitable values from<br>the corresponding row of that table.<br><br>I think there's at least one problem with the Goedel table (A125024):

<br>1500 = 2^2 * 3^1 * 5^3 is the endofunction 2,1,3.  But the equivalent<br>3,2,1 has Goedel value 360.  So, instead of ..., 540, 1500, ..., it<br>should be ..., 360, 540, ....  I'm guessing that you did this table by

<br>hand.  I'll try to find time to program it.<br><br>Franklin T. Adams-Watters<br><br><br>-----Original Message-----<br>From: <a href="mailto:jvospost3@gmail.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

jvospost3@gmail.com</a><br><br>Dear Frank,<br><br>I have a couple of hunded handwritten and hand-drawn pages of digraphs

<br>of endofunctions, and am waiting for my son to get back from his ski<br>trip to do another rewrite of our paper on them.<br><br>For each endofunction through n=7 nodes, I have a drawing, and a table<br>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.

<br><br>I can describe each (up to isomorphism) endofunction on n nodes by<br>picking a specific labeling from [n] = {1,2,...,n}, count indegrees of<br>each node, and then throw away the labels.<br><br>n=0, the null graph can formally be said to have one node with indegree

<br>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 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,

<br><br>Jonathan<br><br><br>On 12/28/06, <a href="mailto:franktaw@netscape.net" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">franktaw@netscape.net</a> <<a href="mailto:franktaw@netscape.net" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

franktaw@netscape.net</a> > wrote:Given<br>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.However" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.research.att.com/~njas/sequences/A019575.However

</a>, if the<br>points are not labeled, the table starts:

1 21 331 5 1031 7 24 1231 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 33<br>1 675<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> .<br><br>These are hand-calculated; I have done some cross-checks, so I have a

<br>fair degree of confidence in them, but not 100%.<br><br>I would appreciate it if someone could verify these and - even better -<br>extend them.I then plan to submit them.<br><br>Franklin T. Adams-Watters<br><br><br><br>

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

<br>

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