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

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,1

Comments

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.

Links

Table of n, a(n) for n=4..44.

Gerry Myerson, Problems 2004

Index entries for sequences computed from indices in prime factorization

Example

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 |
  +---------------------+------------------+---------------------------+

Prog

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

Crossrefs

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

Sequence in context: A235291 A235893 A192791 * A235886 A261191 A260601

Adjacent sequences: A345967 A345968 A345969 * A345971 A345972 A345973

Keyword

nonn,look,tabf,easy

Author

Washington Bomfim, Jul 01 2021

Status

approved