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.
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
Examples
: 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;
Links
- Alois P. Heinz, Rows n = 1..141, flattened
Crossrefs
Programs
-
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 *)