cp's OEIS Frontend

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

%I A244523 #14 Feb 11 2015 06:05:36
%S A244523 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,
%T A244523 178,66,2,0,1,371,170,6,0,1,773,431,21,0,1,1630,1076,63,0,1,3447,2665,
%U A244523 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
%N A244523 Irregular triangle read by rows: T(n,k) is the number of identity trees with n nodes and maximal branching factor k.
%C A244523 Row sums give A004111.
%H A244523 Joerg Arndt and Alois P. Heinz, <a href="/A244523/b244523.txt">Rows n = 1..285, flattened</a>
%e A244523 Triangle starts:
%e A244523 01:  1,
%e A244523 02:  0, 1,
%e A244523 03:  0, 1,
%e A244523 04:  0, 1, 1,
%e A244523 05:  0, 1, 2,
%e A244523 06:  0, 1, 5,
%e A244523 07:  0, 1, 10, 1,
%e A244523 08:  0, 1, 21, 3,
%e A244523 09:  0, 1, 42, 9,
%e A244523 10:  0, 1, 87, 25,
%e A244523 11:  0, 1, 178, 66, 2,
%e A244523 12:  0, 1, 371, 170, 6,
%e A244523 13:  0, 1, 773, 431, 21,
%e A244523 14:  0, 1, 1630, 1076, 63,
%e A244523 15:  0, 1, 3447, 2665, 185, 1,
%e A244523 16:  0, 1, 7346, 6560, 512, 7,
%e A244523 17:  0, 1, 15712, 16067, 1403, 26,
%e A244523 18:  0, 1, 33790, 39219, 3750, 91,
%e A244523 19:  0, 1, 72922, 95476, 9928, 291,
%e A244523 20:  0, 1, 158020, 231970, 25969, 885, 3,
%e A244523 21:  0, 1, 343494, 562736, 67462, 2588, 15,
%e A244523 22:  0, 1, 749101, 1363640, 174039, 7373, 70,
%e A244523 23:  0, 1, 1638102, 3301586, 446884, 20555, 256,
%e A244523 24:  0, 1, 3591723, 7988916, 1142457, 56413, 884,
%e A244523 25:  0, 1, 7893801, 19322585, 2911078, 152812, 2840, 3,
%e A244523 ...
%e A244523 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:
%e A244523 01:  [ . 1 2 3 4 5 6 ]    [ 1 1 1 1 1 1 . ]   1
%e A244523 02:  [ . 1 2 3 4 5 4 ]    [ 1 1 1 2 1 . . ]   2
%e A244523 03:  [ . 1 2 3 4 5 3 ]    [ 1 1 2 1 1 . . ]   2
%e A244523 04:  [ . 1 2 3 4 5 2 ]    [ 1 2 1 1 1 . . ]   2
%e A244523 05:  [ . 1 2 3 4 5 1 ]    [ 2 1 1 1 1 . . ]   2
%e A244523 06:  [ . 1 2 3 4 3 2 ]    [ 1 2 2 1 . . . ]   2
%e A244523 07:  [ . 1 2 3 4 3 1 ]    [ 2 1 2 1 . . . ]   2
%e A244523 08:  [ . 1 2 3 4 2 3 ]    [ 1 2 1 1 . 1 . ]   2
%e A244523 09:  [ . 1 2 3 4 2 1 ]    [ 2 2 1 1 . . . ]   2
%e A244523 10:  [ . 1 2 3 4 1 2 ]    [ 2 1 1 1 . 1 . ]   2
%e A244523 11:  [ . 1 2 3 2 1 2 ]    [ 2 2 1 . . 1 . ]   2
%e A244523 12:  [ . 1 2 3 1 2 1 ]    [ 3 1 1 . 1 . . ]   3
%e A244523 This gives row n=7: [0, 1, 10, 1, 0, 0, ... ].
%p A244523 b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
%p A244523       `if`(i<1, 0, add(binomial(b(i-1$2, k$2), j)*
%p A244523        b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
%p A244523     end:
%p A244523 g:= proc(n) local k; if n=1 then 0 else
%p A244523        for k while T(n, k)>0 do od; k-1 fi
%p A244523     end:
%p A244523 T:= (n, k)-> b(n-1$2, k$2) -`if`(k=0, 0, b(n-1$2, k-1$2)):
%p A244523 seq(seq(T(n, k), k=0..g(n)), n=1..25);
%t A244523 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 *)
%Y A244523 Columns k=0-10 give: A000007, A000012 (for n>0), A245747, A245748, A245749, A245750, A245751, A245752, A245753, A245754, A245755.
%Y A244523 Cf. A004111 (identity trees), A244372 (unlabeled rooted trees by outdegree).
%K A244523 nonn,tabf
%O A244523 1,11
%A A244523 _Joerg Arndt_ and _Alois P. Heinz_, Jul 30 2014