A265127 -id:A265127 - cp's OEIS frontend

A344122 Triangle T(n,k) read by rows in which n-th row gives all tree-able degree sequences S of n nodes encoded as Product_{k in S} prime(k); n >= 2, 1<= k <= A000041(n-2).

4, 12, 40, 36, 112, 120, 108, 352, 336, 400, 360, 324, 832, 1056, 1120, 1008, 1200, 1080, 972, 2176, 2496, 3520, 3136, 3168, 3360, 4000, 3024, 3600, 3240, 2916, 4864, 6528, 8320, 9856, 7488, 10560, 9408, 11200, 9504, 10080, 12000, 9072, 10800, 9720, 8748, 11776, 14592, 21760

Offset: 2

Washington Bomfim, Jun 02 2021

Tree-able degree sequences are degree sequences that can be realized as trees [Stern].

The partitions of n-2 are given in nondecreasing order of length/lex.

			Triangle T(n,k) begins:
n/k 1    2     3 ...
2     4;
3    12;
4    40,   36;
5   112,  120,  108;
6   352,  336,  400,  360,  324;
7   832, 1056, 1120, 1008, 1200, 1080,  972;
8  2176, 2496, 3520, 3136, 3168, 3360, 4000, 3024, 3600, 3240, 2916;
  ...
Row 5 is 112, 120, 108 because prime(1) = 2, prime(2) = 3, prime(3) = 5, and prime(4) = 7. The tree-able degree sequences of 5 nodes, related tree realization and encode are given below.
  [4, 1, 1, 1, 1]     o           7*2*2*2*2 = 112.
                   ( ) ( )
                   o o o o
  [3, 2, 1, 1, 1]        o        5*3*2*2*2 = 120.
                       / | \
                   o--o  o  o
  [2, 2, 2, 1, 1]  o--o--o--o--o  3*3*3*2*2 = 108.

Washington Bomfim, Table of n, a(n) for n = 2..9297 (Rows n = 2..27, flattened)
Samuel Stern, The Tree of Trees: on methods for finding all non-isomorphic tree-realizations of degree sequences, Honors Thesis, Wesleyan University, 2017.
Index entries for sequences computed from indices in prime factorization

Cf. A000041, A000055, A003946 (last terms in rows), A215366, A265127 (first column).

\\ Gives row n of triangle, n >= 2.
Row(n)={my(j=1, V=vector(numbpart(n-2))); forpart(P=n-2,
V[j] = prod(k = 1, #P, prime(P[k] + 1)); V[j] <<= (n-#P); j++ ); V };

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

A344122 Triangle T(n,k) read by rows in which n-th row gives all tree-able degree sequences S of n nodes encoded as Product_{k in S} prime(k); n >= 2, 1<= k <= A000041(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