A250308 -id:A250308 - cp's OEIS frontend

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

Washington Bomfim, Jul 05 2021

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.

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

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

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

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() ) };

A345970 Irregular triangle T(n,k) read by rows in which n-th row lists in colex order all series-reduced tree degree sequences D of n nodes encoded as t = Product_{d in D} prime(d); n >= 4, 1 <= k <= A002865(n-2).

Original entry on oeis.org

40, 112, 352, 400, 832, 1120, 2176, 3520, 3136, 4000, 4864, 8320, 9856, 11200, 11776, 21760, 23296, 30976, 35200, 31360, 40000, 29696, 48640, 60928, 73216, 83200, 98560, 87808, 112000, 63488, 117760, 136192, 191488, 173056, 217600, 232960, 309760, 275968, 352000, 313600, 400000

Offset: 4

Washington Bomfim, Jul 01 2021

Tree degree sequences of n nodes are in one-to-one correspondence with the partitions of n-2, as for instance set out in Myerson's collection of problems [Myerson]. For series-reduced trees, these partitions have no part 1.
Given a term t, the respective degree sequence D is determined by Decode(t). See second (PARI) entry.
A250308(n) = Sum_{k= 1 .. A002865(2*n-2) } ( A345971(2*n,k) * odd( Decode( T(2*n,k) ) ), where odd(D) is 1 if all d in D are odd, and 0 otherwize.

			Triangle begins:
  n \ k|  1    2 ...           n \ k| 1                2            ...
  -----+-------------          -----+-----------------------------------
  4    |   40;                 4    |       [3,1,1,1];
  5    |  112;                 5    |     [4,1,1,1,1];
  6    |  352,  400;    <=>    6    |   [5,1,1,1,1,1],   [3,3,1,1,1,1];
  7    |  832, 1120;           7    | [6,1,1,1,1,1,1], [4,3,1,1,1,1,1];
  ...                          ...
Row n = 7 follows from table
                                                                         .
  +---------------------+------------------+---------------------------+
  | Partitions of n-2 = |                  |                           |
  | 5 without parts 1   | Degree sequences |       Encoding            |
  +---------------------+------------------+---------------------------+
  |                 [5] |    6,1,1,1,1,1,1 |            prime(6) * 2^6 |
  |              [2, 3] |    4,3,1,1,1,1,1 | prime(4) * prime(3) * 2^5 |
  +---------------------+------------------+---------------------------+

Gerry Myerson, Problems 2004
Index entries for sequences computed from indices in prime factorization

Cf. A002865 (row widths), A265127 (column k=1), A345971 (number of trees by degree sequence), A344122 (free tree degree sequences), A250308.

Row(n) = {my(j=0, V = vector(numbpart(n-2) - numbpart(n-3)));
forpart(P=n-2, V[j++] = prod(k=1,#P, prime(P[k]+1)) << (n-#P),[2, n-2]); V};

Decode(t) = {my(V = [], i = 1, p); while(t > 1, p = prime(i); while(t % p == 0, t /= p; V = concat(V, Vec(i)) ); i++); vecsort(V, (x,y)->y-x) };

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A345970 Irregular triangle T(n,k) read by rows in which n-th row lists in colex order all series-reduced tree degree sequences D of n nodes encoded as t = Product_{d in D} prime(d); n >= 4, 1 <= k <= A002865(n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI