login
A372594
Irregular triangle read by rows, where the n-th row gives the number of steps in the hydra game (the version described in A180368) when the initial hydra is each of the A000108(n) ordered trees with n edges (ordered by lexicographic order of their corresponding Dyck words as in A063171).
4
0, 1, 2, 3, 3, 4, 4, 7, 8, 4, 5, 5, 8, 9, 5, 6, 8, 15, 16, 9, 17, 37, 38, 5, 6, 6, 9, 10, 6, 7, 9, 16, 17, 10, 18, 38, 39, 6, 7, 7, 10, 11, 9, 10, 16, 31, 32, 17, 33, 69, 70, 10, 11, 18, 35, 36, 38, 75, 614, 615, 39, 77, 631, 161914, 161915
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
Last elements on each row give A180368.
Sequence in context: A095916 A130121 A007898 * A367009 A110533 A131282
KEYWORD
nonn,tabf
AUTHOR
STATUS
approved