OFFSET
0,10
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.
LINKS
Peter Luschny, Rows n = 0..140, flattened.
Peter Luschny, Python implementation.
FORMULA
The rows accumulate the rows of A034781.
T(n, k) = (1/(n-1)) * Sum_{j=1..n-1} T(j, k) * H(n-j, k-1) for n >= 2 and k > 1, where H(n, k) = Sum_{d|n} d*T(d, k). T(n, 0) = 0 and T(1, k) = 1 for k >= 1. - Peter Luschny, Aug 19 2026
EXAMPLE
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]
.
This is a modified form of the list given by Joerg Arndt in A000081, illustrating the successive construction of row 6 in the table: at each step, the maximal permissible value of a component is increased by 1. Then T(n, k) is the number of parenthesis tuples whose largest component does not exceed k.
--
20: [ 1 2 2 2 2 2 ] (()()()()()) * * * * *
--
14: [ 1 2 3 3 3 3 ] ((()()()())) * * * *
15: [ 1 2 3 3 3 2 ] ((()()())()) * * * *
16: [ 1 2 3 3 2 3 ] ((()())(())) * * * *
17: [ 1 2 3 3 2 2 ] ((()())()()) * * * *
18: [ 1 2 3 2 3 2 ] ((())(())()) * * * *
19: [ 1 2 3 2 2 2 ] ((())()()()) * * * *
--
06: [ 1 2 3 4 4 4 ] (((()()()))) * * *
07: [ 1 2 3 4 4 3 ] (((()())())) * * *
08: [ 1 2 3 4 4 2 ] (((()()))()) * * *
09: [ 1 2 3 4 3 4 ] (((())(()))) * * *
10: [ 1 2 3 4 3 3 ] (((())()())) * * *
11: [ 1 2 3 4 3 2 ] (((())())()) * * *
12: [ 1 2 3 4 2 3 ] (((()))(())) * * *
13: [ 1 2 3 4 2 2 ] (((()))()()) * * *
--
02: [ 1 2 3 4 5 5 ] ((((()())))) * *
03: [ 1 2 3 4 5 4 ] ((((())()))) * *
04: [ 1 2 3 4 5 3 ] ((((()))())) * *
05: [ 1 2 3 4 5 2 ] ((((())))()) * *
--
01: [ 1 2 3 4 5 6 ] (((((()))))) *
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
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
Peter Luschny, Aug 29 2024
STATUS
approved