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

Adjacent sequences: A244520 A244521 A244522 * A244524 A244525 A244526

Keyword

nonn,tabf

Author

Joerg Arndt and Alois P. Heinz, Jul 30 2014

Status

approved