login
A244523
Irregular triangle read by rows: T(n,k) is the number of identity trees with n nodes and maximal branching factor k.
10
1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 2, 0, 1, 5, 0, 1, 10, 1, 0, 1, 21, 3, 0, 1, 42, 9, 0, 1, 87, 25, 0, 1, 178, 66, 2, 0, 1, 371, 170, 6, 0, 1, 773, 431, 21, 0, 1, 1630, 1076, 63, 0, 1, 3447, 2665, 185, 1, 0, 1, 7346, 6560, 512, 7, 0, 1, 15712, 16067, 1403, 26, 0, 1, 33790, 39219, 3750, 91, 0, 1, 72922, 95476, 9928, 291
OFFSET
1,11
COMMENTS
Row sums give A004111.
LINKS
Joerg Arndt and Alois P. Heinz, Rows n = 1..285, flattened
EXAMPLE
Triangle starts:
01: 1,
02: 0, 1,
03: 0, 1,
04: 0, 1, 1,
05: 0, 1, 2,
06: 0, 1, 5,
07: 0, 1, 10, 1,
08: 0, 1, 21, 3,
09: 0, 1, 42, 9,
10: 0, 1, 87, 25,
11: 0, 1, 178, 66, 2,
12: 0, 1, 371, 170, 6,
13: 0, 1, 773, 431, 21,
14: 0, 1, 1630, 1076, 63,
15: 0, 1, 3447, 2665, 185, 1,
16: 0, 1, 7346, 6560, 512, 7,
17: 0, 1, 15712, 16067, 1403, 26,
18: 0, 1, 33790, 39219, 3750, 91,
19: 0, 1, 72922, 95476, 9928, 291,
20: 0, 1, 158020, 231970, 25969, 885, 3,
21: 0, 1, 343494, 562736, 67462, 2588, 15,
22: 0, 1, 749101, 1363640, 174039, 7373, 70,
23: 0, 1, 1638102, 3301586, 446884, 20555, 256,
24: 0, 1, 3591723, 7988916, 1142457, 56413, 884,
25: 0, 1, 7893801, 19322585, 2911078, 152812, 2840, 3,
...
The A004111(7) = 12 level-sequences and the branching sequences for the identity trees with 7 nodes are (dots for zeros), together with the maximal branching factors, are:
01: [ . 1 2 3 4 5 6 ] [ 1 1 1 1 1 1 . ] 1
02: [ . 1 2 3 4 5 4 ] [ 1 1 1 2 1 . . ] 2
03: [ . 1 2 3 4 5 3 ] [ 1 1 2 1 1 . . ] 2
04: [ . 1 2 3 4 5 2 ] [ 1 2 1 1 1 . . ] 2
05: [ . 1 2 3 4 5 1 ] [ 2 1 1 1 1 . . ] 2
06: [ . 1 2 3 4 3 2 ] [ 1 2 2 1 . . . ] 2
07: [ . 1 2 3 4 3 1 ] [ 2 1 2 1 . . . ] 2
08: [ . 1 2 3 4 2 3 ] [ 1 2 1 1 . 1 . ] 2
09: [ . 1 2 3 4 2 1 ] [ 2 2 1 1 . . . ] 2
10: [ . 1 2 3 4 1 2 ] [ 2 1 1 1 . 1 . ] 2
11: [ . 1 2 3 2 1 2 ] [ 2 2 1 . . 1 . ] 2
12: [ . 1 2 3 1 2 1 ] [ 3 1 1 . 1 . . ] 3
This gives row n=7: [0, 1, 10, 1, 0, 0, ... ].
MAPLE
b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
`if`(i<1, 0, add(binomial(b(i-1$2, k$2), j)*
b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
end:
g:= proc(n) local k; if n=1 then 0 else
for k while T(n, k)>0 do od; k-1 fi
end:
T:= (n, k)-> b(n-1$2, k$2) -`if`(k=0, 0, b(n-1$2, k-1$2)):
seq(seq(T(n, k), k=0..g(n)), n=1..25);
MATHEMATICA
b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[b[i-1, i-1, k, k], j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]]]; g[n_] := If[ n == 1 , 0, For[k=1, T[n, k]>0 , k++]; k-1]; T[n_, k_] := b[n-1, n-1, k, k] - If[k == 0, 0, b[n-1, n-1, k-1, k-1]]; Table[Table[T[n, k], {k, 0, g[n]}], {n, 1, 25}] // Flatten (* Jean-François Alcover, Feb 11 2015, after Maple *)
CROSSREFS
Columns k=0-10 give: A000007, A000012 (for n>0), A245747, A245748, A245749, A245750, A245751, A245752, A245753, A245754, A245755.
Cf. A004111 (identity trees), A244372 (unlabeled rooted trees by outdegree).
Sequence in context: A337085 A209687 A108263 * A325304 A134433 A125183
KEYWORD
nonn,tabf
AUTHOR
Joerg Arndt and Alois P. Heinz, Jul 30 2014
STATUS
approved