Endofunctions by indegree

[Jonathan Post]

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, 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 (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 .
>
> 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/b3ded0cb/attachment-0002.htm>