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

Author

Alois P. Heinz, Feb 28 2015

Keywords

• nonn
• tabl

Comments

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

Examples

			:    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, ...
		

Links

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

Crossrefs

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

Main diagonal gives A000081.

Cf. A255704.

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