OFFSET
0,3
COMMENTS
Here, in contrast to A180368, the rightmost head is always chopped off. Equivalently, chop off the leftmost head but interpret the Dyck words as describing the trees from the right to the left (or sort the Dyck words colexicographically).
FORMULA
T(n,k) = T(n-1,k)+1 if 1 <= k <= A000108(n-1).
EXAMPLE
Triangle begins:
0;
1;
2, 3;
3, 4, 4, 7, 8;
4, 5, 5, 8, 9, 5, 6, 8, 15, 16, 9, 17, 37, 38;
...
In the examples below, the hydra games for some initial trees are shown. The root is denoted by "R", internal nodes by "o", the head to be chopped off by "X", other heads by "H". Numbers below the arrows show how many steps that are required to go from the tree on the left to the tree on the right.
(n,k) = (2,2), corresponding to the 2nd Dyck word on 2 pairs of brackets, "(())":
X
|
o H X X
| |/ |
R => R => R => R
T(2,2) = 1 + 1 + 1 = 3.
.
(n,k) = (3,4), corresponding to the 4th Dyck word on 3 pairs of brackets, "(()())":
H X H X
\ / \ /
o o o
\ \ /
R => R => R
T(3,4) = 1 + 2*T(2,2) = 7.
.
(n,k) = (4,10), corresponding to the 10th Dyck word on 4 pairs of brackets, "(()(()))":
X
|
o H X H H
| |/ | |
H--o H--o H--o o--X
\ \ \ /
R => R => R => R
T(4,10) = 1 + 1 + 2*T(3,4) = 16.
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Pontus von Brömssen, May 06 2024
STATUS
approved