A375467 Triangle read by rows: Number of unlabeled rooted trees with n vertices where the level of a vertex is bounded by k.

0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 3, 4, 0, 0, 1, 5, 8, 9, 0, 0, 1, 7, 15, 19, 20, 0, 0, 1, 11, 29, 42, 47, 48, 0, 0, 1, 15, 53, 89, 108, 114, 115, 0, 0, 1, 22, 98, 191, 252, 278, 285, 286, 0, 0, 1, 30, 177, 402, 582, 676, 710, 718, 719

Offset: 0

Author

Peter Luschny, Aug 29 2024

Keywords

• nonn
• tabl

Comments

The level of a vertex is the number of vertices in the path from the root to the vertex, the level of the root is 1.

Examples

			Triangle starts:
  [0] [0]
  [1] [0, 1]
  [2] [0, 0, 1]
  [3] [0, 0, 1,  2]
  [4] [0, 0, 1,  3,  4]
  [5] [0, 0, 1,  5,  8,   9]
  [6] [0, 0, 1,  7, 15,  19,  20]
  [7] [0, 0, 1, 11, 29,  42,  47,  48]
  [8] [0, 0, 1, 15, 53,  89, 108, 114, 115]
  [9] [0, 0, 1, 22, 98, 191, 252, 278, 285, 286]
		

Crossrefs

Cf. A000081 (main diagonal), A375468 (row sums), A034781.

Programs

Maple

div := n -> numtheory:-divisors(n):
H := proc(n, k) option remember; local d; add(d * T(d, k), d = div(n)) end:
T := proc(n, k) option remember; local i; if n = 1 then ifelse(k > 0, 1, 0) else add(T(i, k) * H(n - i, k - 1), i = 1..n - 1) / (n - 1) fi end:
seq(print(seq(T(n, k), k = 0..n)), n = 0..9):  # Peter Luschny, Sep 11 2024

Python

from functools import cache
@cache
def Divisors(n: int) -> list[int]:
    return [d for d in range(n, 0, -1) if n % d == 0]
@cache
def H(n: int, k: int) -> int:
    return sum(d * T(d, k) for d in Divisors(n))
@cache
def T(n: int, k: int) -> int:
    if k == 0: return 0
    if n == 1: return int(k > 0)
    return sum(T(i, k) * H(n - i, k - 1)
           for i in range(1, n) ) // (n - 1)
for n in range(10): print([T(n, k) for k in range(n + 1)])
# Peter Luschny, Sep 11 2024

Formula

The rows accumulate the rows of A034781.