login
Number T(n,k) of rooted trees with n nodes such that k equals the maximal number of subtrees extending from the same node and having the same number of nodes; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.
13

%I #21 May 27 2019 08:57:02

%S 1,0,1,0,1,1,0,2,1,1,0,3,4,1,1,0,6,9,3,1,1,0,12,22,9,3,1,1,0,25,54,23,

%T 8,3,1,1,0,51,139,60,23,8,3,1,1,0,111,346,166,61,22,8,3,1,1,0,240,892,

%U 447,167,61,22,8,3,1,1,0,533,2290,1219,461,168,60,22,8,3,1,1

%N Number T(n,k) of rooted trees with n nodes such that k equals the maximal number of subtrees extending from the same node and having the same number of nodes; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

%C T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k < n. T(n,k) = 0 for k >= n.

%H Alois P. Heinz, <a href="/A318754/b318754.txt">Rows n = 1..200, flattened</a>

%F T(n,k) = A318753(n,k) - A318753(n,k-1) for k > 0, A(n,0) = A063524(n).

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 1, 1;

%e 0, 2, 1, 1;

%e 0, 3, 4, 1, 1;

%e 0, 6, 9, 3, 1, 1;

%e 0, 12, 22, 9, 3, 1, 1;

%e 0, 25, 54, 23, 8, 3, 1, 1;

%e 0, 51, 139, 60, 23, 8, 3, 1, 1;

%e 0, 111, 346, 166, 61, 22, 8, 3, 1, 1;

%p g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(

%p binomial(g(i-1$2, k)+j-1, j)*g(n-i*j, i-1, k), j=0..min(k, n/i))))

%p end:

%p T:= (n, k)-> g(n-1$2, k) -`if`(k=0, 0, g(n-1$2, k-1)):

%p seq(seq(T(n, k), k=0..n-1), n=1..14);

%t g[n_, i_, k_] := g[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[g[i - 1, i - 1, k] + j - 1, j]*g[n - i*j, i - 1, k], {j, 0, Min[k, n/i]}]]];

%t T[n_, k_] := g[n - 1, n - 1, k] - If[k == 0, 0, g[n - 1, n - 1, k - 1]];

%t Table[T[n, k], {n, 1, 14}, {k, 0, n - 1}] // Flatten (* _Jean-François Alcover_, May 27 2019, after _Alois P. Heinz_ *)

%Y Columns k=0-10 give: A063524, A032305 (for n>1), A318817, A318818, A318819, A318820, A318821, A318822, A318823, A318824, A318825.

%Y Row sums give A000081.

%Y T(2n+2,n+1) give A255705.

%Y Cf. A318753.

%K nonn,tabl

%O 1,8

%A _Alois P. Heinz_, Sep 02 2018