login
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).
1
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.
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
KEYWORD
nonn,look,tabf,easy
AUTHOR
Washington Bomfim, Jul 01 2021
STATUS
approved