A244523 Irregular triangle read by rows: T(n,k) is the number of identity trees with n nodes and maximal branching factor k.

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

Author

Joerg Arndt and Alois P. Heinz, Jul 30 2014

Keywords

• nonn
• tabf

Comments

Row sums give A004111.

Examples

			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, ... ].
		

Links

• Joerg Arndt and Alois P. Heinz, Rows n = 1..285, flattened

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

Programs

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