A345971 Irregular triangle T(n,k) read by rows in which n-th row lists numbers of series-reduced trees realized by respective degree sequences in n-th row of A345970; n >= 4, 1 <= k <= A002865(n-2).

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 3, 1, 4, 1, 1, 1, 1, 1, 2, 3, 2, 2, 4, 6, 2, 1, 1, 1, 1, 1, 2, 3, 3, 2, 2, 4, 9, 4, 8, 1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 2, 3, 1, 4, 9, 6, 9, 2, 8, 14, 4, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 2, 3, 2, 2, 4, 9, 9, 9, 9, 4, 8, 25, 14, 15

Offset: 4

Author

Washington Bomfim, Jul 05 2021

Keywords

• nonn
• tabf

Comments

The first floor((n-2)/2) terms of n-th row are all 1 thus the first floor((n-2)/2) degree sequences of n-th row of A345970 have only one realization.

Let a "unigraph" be a graph which is the only realization of its degree sequence. Among all series-reduced trees on n vertices we have floor((n-2)/2) + [n>=8] * [(n-8) == 0 (mod 3)] unigraphs.

Let T be a series-reduced tree of diameter dT, with h nodes of degree >= 3, and degree sequence D. If h <= 2, dT <= 3, and T is a unigraph [R. H. Johnson Corollary 2.3]. For each degree sequence the value of h is equal to the number of parts of a unique partition [Myerson], thus the number of unigraphs would be equal to the number of partitions (without parts 1) of n-2 with at most 2 parts, which is floor((n-2)/2). Degree sequences of the form [d,d,d,1,..,1] give an additional unigraph when n >= 8 and (n-8) == 0 (mod 3). These unigraphic sequences can be depicted as:

||_| , |_|| , ...

| | |

A250308(n) = Sum_{ k= 1 .. A002865(2*n-2) } ( T(2*n,k) * odd( Decode( A345970(2*n, k) ) ), where odd(D) is 1 if all d in D are odd, and 0 otherwize.

Examples

			Row number 9 is {1, 1, 1, 2} because the 9th row of A345970 is {4864, 8320, 9856, 11200} which can be decoded (using Decode() of A345970) to the 4-degree sequences [8,1,1,1,1,1,1,1,1], which obviously has just 1 realization, [6,3,1,1,1,1,1,1,1], [5,4,1,1,1,1,1,1,1], that also have one, and [4,3,3,1,1,1,1,1,1] which realizes the 2 trees:
.
       *  *  *            *  *  *
       |  |  |            |  |  |
    *--0--*--*         *--*--0--*
       |     |               |  |
       *     *               *  *
.
Triangle begins
   n \ k 1  2  3  4  5  6  7  8  9 10 11 12
    4    1;
    5    1;
    6    1, 1;
    7    1, 1;
    8    1, 1, 1, 1;
    9    1, 1, 1, 2;
   10    1, 1, 1, 1, 2, 2, 2;
   11    1, 1, 1, 1, 2, 3, 1, 4;
   12    1, 1, 1, 1, 1, 2, 3, 2, 2, 4, 6, 2;
   ...
		

Links

• Nima Amini, Not That Good, Will Hunting
• R. H. Johnson, Properties of unique realizations-a survey, Discrete Mathematics, Volume 31 January, 1980 pp 185-192.
• B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.
• Gerry Myerson, Problems2004
• Index entries for sequences related to trees

Crossrefs

Cf. A000014 (row sums), A002865 (row widths), A345970 (encoded degree sequences), A250308.

Programs

PARI

D_Generator(n) = { my(D = vectorsmall(n), j);
M = Map();                                \\ For each partition of n-2, "P",
forpart( P = n-2,                         \\ P without parts 1, make D =
   for(i = 1, n-#P, D[i] = 1); j = n-#P;  \\ [1..1 0..0], n-#P terms 1, and
   for(i = 1,   #P, D[j++] = P[i] + 1);   \\ #p terms 0. Complete D.
   mapput(M, D, 0) , [2, n-2] )        \\ store D.
};
EdgesList2D(n, Tr) = {my(D = vectorsmall(n), E = strsplit(Tr, "  "), u_v);
for(j = 1, n-1, u_v = strsplit(E[j], " "); u_v = eval(u_v);
   D[ u_v[1]+1 ]++; D[ u_v[2]+1 ]++); vecsort(D) };
                                      \\ Using files hitree4.txt etc from McKay.
Rows(r1, r2) = {my(Trees, D, j, C); for(n = r1, r2,
Trees = readstr(Str("hitree", n, ".txt")); D_Generator(n);
for(i = 1, #Trees, D = EdgesList2D(n, Trees[i]); j = mapget(M, D); mapput(~M, D, j+1));
C = Mat(M)[, 2]; print1(n" "); for(i = 1, #C, print1(C[i]", ")); print() ) };