A255704 - OEIS

%I #23 Sep 05 2018 12:33:34

%S 1,0,1,0,1,1,0,2,1,1,0,4,3,1,1,0,8,7,3,1,1,0,17,18,8,3,1,1,0,36,45,21,

%T 8,3,1,1,0,79,116,56,22,8,3,1,1,0,175,298,152,59,22,8,3,1,1,0,395,776,

%U 413,163,60,22,8,3,1,1,0,899,2025,1131,450,166,60,22,8,3,1,1

%N Number T(n,k) of n-node rooted trees in which the maximal number of nodes in paths starting at a leaf and ending at the first branching node or at the root equals k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

%H Alois P. Heinz, <a href="/A255704/b255704.txt">Rows n = 1..141, flattened</a>

%F T(n,1) = A255636(n,1), T(n,k) = A255636(n,k) - A255636(n,k-1) for k>1.

%e :    o      o     o         o     o     o     o

%e :  /( )\   /|\   / \       / \    |     |     |

%e : o o o o o o o o   o     o   o   o     o     o

%e : |       | |   |  / \   / \     /|\   / \    |

%e : o       o o   o o   o o   o   o o o o   o   o

%e :                       |       |     |   |  / \

%e :                       o       o     o   o o   o

%e :                                           |

%e : T(6,3) = 7                                o

%e Triangle T(n,k) begins:

%e   1;

%e   0,   1;

%e   0,   1,   1;

%e   0,   2,   1,   1;

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

%e   0,   8,   7,   3,  1,  1;

%e   0,  17,  18,   8,  3,  1, 1;

%e   0,  36,  45,  21,  8,  3, 1, 1;

%e   0,  79, 116,  56, 22,  8, 3, 1, 1;

%e   0, 175, 298, 152, 59, 22, 8, 3, 1, 1;

%p with(numtheory):

%p g:= proc(n, k) option remember; `if`(n=0, 1, add(add(d*(g(d-1, k)-

%p       `if`(d=k, 1, 0)), d=divisors(j))*g(n-j, k), j=1..n)/n)

%p     end:

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

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

%t g[n_, k_] := g[n, k] = If[n == 0, 1, Sum[DivisorSum[j, #*(g[#-1, k] - If[# == k, 1, 0])&] * g[n-j, k], {j, 1, n}]/n];

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

%t Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Mar 24 2017, translated from Maple *)

%Y Columns k=1-10 give: A063524, A002955 (for n>1), A318899, A318900, A318901, A318902, A318903, A318904, A318905, A318906.

%Y Row sums give A000081.

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

%Y Cf. A255636.

%K nonn,tabl

%O 1,8

%A _Alois P. Heinz_, Mar 02 2015