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,8

Links

Alois P. Heinz, Rows n = 1..141, flattened

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

Adjacent sequences: A255701 A255702 A255703 * A255705 A255706 A255707

Keyword

nonn,tabl

Author

Alois P. Heinz, Mar 02 2015

Status

approved