login
A255704
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.
11
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, 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, 413, 163, 60, 22, 8, 3, 1, 1, 0, 899, 2025, 1131, 450, 166, 60, 22, 8, 3, 1, 1
OFFSET
1,8
LINKS
FORMULA
T(n,1) = A255636(n,1), T(n,k) = A255636(n,k) - A255636(n,k-1) for k>1.
EXAMPLE
: o o o o o o o
: /( )\ /|\ / \ / \ | | |
: o o o o o o o o o o o o o o
: | | | | / \ / \ /|\ / \ |
: o o o o o o o o o o o o o o
: | | | | / \
: o o o o o o
: |
: T(6,3) = 7 o
Triangle T(n,k) begins:
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, 8, 3, 1, 1;
0, 79, 116, 56, 22, 8, 3, 1, 1;
0, 175, 298, 152, 59, 22, 8, 3, 1, 1;
MAPLE
with(numtheory):
g:= proc(n, k) option remember; `if`(n=0, 1, add(add(d*(g(d-1, k)-
`if`(d=k, 1, 0)), d=divisors(j))*g(n-j, k), j=1..n)/n)
end:
T:= (n, k)-> g(n-1, k) -`if`(k=1, 0, g(n-1, k-1)):
seq(seq(T(n, k), k=1..n), n=1..14);
MATHEMATICA
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[n_, k_] := g[n-1, k] - If[k == 1, 0, g[n-1, k-1]];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 24 2017, translated from Maple *)
CROSSREFS
Columns k=1-10 give: A063524, A002955 (for n>1), A318899, A318900, A318901, A318902, A318903, A318904, A318905, A318906.
Row sums give A000081.
T(2*n+1,n+1) gives A255705.
Cf. A255636.
Sequence in context: A135221 A318686 A214546 * A191347 A106234 A238125
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Mar 02 2015
STATUS
approved