A255636 Number A(n,k) of n-node rooted trees with a forbidden limb of length k; square array A(n,k), n>=1, k>=1, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 2, 0, 1, 1, 2, 3, 4, 0, 1, 1, 2, 4, 7, 8, 0, 1, 1, 2, 4, 8, 15, 17, 0, 1, 1, 2, 4, 9, 18, 35, 36, 0, 1, 1, 2, 4, 9, 19, 43, 81, 79, 0, 1, 1, 2, 4, 9, 20, 46, 102, 195, 175, 0, 1, 1, 2, 4, 9, 20, 47, 110, 251, 473, 395, 0

Offset

1,13

Comments

Any rootward k-node path starting at a leaf contains the root or a branching node.

Links

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

Example

:    o      o        o      o    o       o      o    o
:  /(|)\    |       / \    /|\   |       |     / \   |
: o ooo 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
: A(6,2) = 8                                        / \
:                                                  o   o
Square array A(n,k) begins:
  1,   1,   1,   1,   1,   1,   1,   1,   1,   1, ...
  0,   1,   1,   1,   1,   1,   1,   1,   1,   1, ...
  0,   1,   2,   2,   2,   2,   2,   2,   2,   2, ...
  0,   2,   3,   4,   4,   4,   4,   4,   4,   4, ...
  0,   4,   7,   8,   9,   9,   9,   9,   9,   9, ...
  0,   8,  15,  18,  19,  20,  20,  20,  20,  20, ...
  0,  17,  35,  43,  46,  47,  48,  48,  48,  48, ...
  0,  36,  81, 102, 110, 113, 114, 115, 115, 115, ...
  0,  79, 195, 251, 273, 281, 284, 285, 286, 286, ...
  0, 175, 473, 625, 684, 706, 714, 717, 718, 719, ...

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:
A:= (n, k)-> g(n-1, k):
seq(seq(A(n, 1+d-n), n=1..d), d=1..14);

Mathematica

g[n_, k_] := g[n, k] = If[n == 0, 1, Sum[Sum[d*(g[d - 1, k] - If[d == k, 1, 0]), {d, Divisors[j]}]*g[n - j, k], {j, 1, n}]/n]; A[n_, k_] := g[n - 1, k]; Table[Table[A[n, 1 + d - n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

Crossrefs

Columns k=1-10 give: A063524, A002955, A052321, A052327, A052328, A052329, A255637, A255638, A255639, A255640.

Main diagonal gives A000081.

Cf. A255704.

Sequence in context: A286653 A283308 A339959 * A292085 A262163 A293112

Adjacent sequences: A255633 A255634 A255635 * A255637 A255638 A255639

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 28 2015

Status

approved