Endofunctions by indegree

Fri Dec 29 05:15:27 CET 2006

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.

My arbitrary designations of n+2 are:

A_2: (1,2)->(1,2) has 0 nodes of indegree 0 and 2 of indegree 1.

B_2: (1,2)->(2,2) has 1 node of indegree 0 and 1 of indegree 2.

C_2: (1,2)->(2,1) has 0 nodes of indegree 0 and 2 of indegree 1.

One typo corrected from before:

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_3 (1,2,3)->(1,2,3) :0,3,0,0
B_3 (1,2,3)->(2,3,1) :0,3,0,0
C_3 (1,2,3)->(1,3,2) :0,3,0,0
D_3 (1,2,3)->(1,2,1) :1,1,1,0
E_3 (1,2,3)->(1,3,1) :0,1,2,0
F_3 (1,2,3)->(3,3,3) :2,0,0,1
G_3 (1,2,3)->(2,1,1) :1,1,1,0
-------------
7:                           4,12,4,1 column sums

We can count off how many rows correspond to any given partition of n.

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
H_4 (1,2,3,4)->(2,3,4,2) ,
I_4 = B_2 + B_2
J_4 (1,2,3,4)->(2,3,4,4),
K_4 (1,2,3,4)->(3,3,4,4),
L_4 (1,2,3,4)_>(4,3,4,4),
M_4 =b_2 + C_2,
N_4 = B_2 x B_2,
O_4 (1,2,3,4)->(2,3, 4,3),
P_4 = B_2 x C_2,
Q_4 (1,2,3,4)-(3,3,4,3)
R_4 = C_2 + C_2,
S_4 (1,2,3,4)->(2,3,4,1)
where the "x" means categorical product, and "+" means direct sum.

We can classify these by cycle index, the number of cycles of length
1,2,...,n
A_4: 4,0,0,0
B_4: 1,0,1,0
C_4: 2,1,0,0
D_4: 3,0,0,0
E_4: 2,0,0,0
F_4: 2,0,0,0
G_4: 1,1,0,0
H_4: 0,0,1,0
I_4: 2,0,0,0
J_4: 1,0,0,0
K_4: 1,0,0,0
L_4: 1,0,0,0
M_4: 1,1,0,0
N_4: 1,0,0,0
O_4: 0,1,0,0
P_4: 0,1,0,0
Q_4: 0,1,0,0
R_4: 0,2,0,0
S_4: 0,0,0,1
------------------
19    22,8,2,1  column sums

6 of these are loop-free, 1 is arc-free, 12 are mixed

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

-- Jonathan Vos Post

On 12/28/06, Jonathan Post <jvospost3 at gmail.com> wrote:
>
> 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<http://www.research.att.com/%7Enjas/sequences/A019575>.  However,
> > if the
> > 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.
> >
> > 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 3  3
> > 1 6  7  5
> > 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/e6071109/attachment-0003.htm>