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

Author

Alois P. Heinz, Mar 02 2015

Keywords

• nonn
• tabl

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

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.

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 *)

Formula

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