Endofunctions by indegree

Fri Dec 29 06:50:25 CET 2006

Mean Cycle Length and Mean Number of Predecessors
*
*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.

The [see handwritten drawings and tables on yellow pad] calculated mean
cycle length of prime endomorphisms on n vertices, 1<n<8.

mu(2) = 3/2 = 1.5
mu(3) = 9/4 = 2.25
mu(4) = 15/7 = 2.143
mu(5) = 40/21 = 1.905
mu(6) = 55/23 = 2.391
mu(7) = 110/42 = 2.619

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.

One can also calculate the "average tail length" of the direct graphs of
prime endofunctions.

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

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

For n=2
B_2 (1,2)->(2,2): 1 has 0 preimages, 2 has 2, total = 2
C_2 (1,2)->(2,1): 1 has 2 primages, 2 has 2 preimages, total = 4
so Omega(2) = ((2+4)/2) = 3.

n = 3
(1,2,3)->(2,3,3) preimages = 0,1,2 total = 4
(1,2,3)->(2,2,2) preimages 0,0,0 total = 3
(1,2,3)->(2,3,2) preeimages 0,2,3 total = 5
(1,2,3)->(2,3,1) preimages 3,3,3 total = 9
so Omega(3) = ((4+3+5+9)/6) = 3.5

Coutier & Holden, p.2 rephrases:
"... x is a terminal node if f^(-1)=null set.  A node is an image node if it
is not a terminal node..."

after a bit of computing...

pi(2) = 6/2 = 3
pi(3) = 21/6 = 3.5
pi(4) = 63/7 = 9
pi(5) = 234/21 = 11.1429
pi(6) = 396/23 = 17.217391
pi(7) = 933/42 = 22.214285
These sequences of numerators and denominators are not "frac" seqs yet in
OEIS.

On 12/28/06, Jonathan Post <jvospost3 at gmail.com> wrote:
>
> 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.
>
> On 12/28/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
> >
> > Mostly to Jonathon,
> >
> > 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]).
> >
> > Note that my second table, with the partitions, is really the most
> > fundamental; the other two can obtained by summing suitable values from
> > the corresponding row of that table.
> >
> > I think there's at least one problem with the Goedel table (A125024):
> > 1500 = 2^2 * 3^1 * 5^3 is the endofunction 2,1,3.  But the equivalent
> > 3,2,1 has Goedel value 360.  So, instead of ..., 540, 1500, ..., it
> > should be ..., 360, 540, ....  I'm guessing that you did this table by
> > hand.  I'll try to find time to program it.
> >
> > Franklin T. Adams-Watters
> >
> >
> > -----Original Message-----
> > From: jvospost3 at gmail.com
> >
> > 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.
> >
> > n=1, (1)->(1) has 0 nodes of indegree 0 and 1 of indegree 1.
> >
> > n=2, there are 3 endofunctions:
> >
> > (1,2)->(1,2) has 0 nodes of indegree 0 and 2 of indegree 1.
> >
> > (1,2)->(2,2) has 1 node of indegree 0 and 1 of indegree 2.
> >
> > (1,2)->(2,1) has 0 nodes of indegree 0 and 2 of indegree 1.
> >
> > n=3, there are 7 endofunctions:
> > My notes label them A-G
> > The table of the number of nodes of indegree k for k = 0,1,2,3 is:
> > A:0,3,0,0
> > 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,
> >
> > Jonathan
> >
> >
> > On 12/28/06, franktaw at netscape.net <franktaw at netscape.net > wrote: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<http://www.research.att.com/%7Enjas/sequences/A019575.However>,
> > if the
> > 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.
> >
> > 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
> > <http://www.research.att.com/%7Enjas/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 33
> > 1 675
> > 1 7 18 14 7
> >
> > Row sums for all three tables are in
> > http://www.research.att.com/~njas/sequences/A001372<http://www.research.att.com/%7Enjas/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.
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061228/aa3a07bc/attachment-0002.htm>