|
%I #5 May 08 2024 14:56:37
%S 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,
%T 16,17,10,18,38,39,6,7,7,10,11,9,10,16,31,32,17,33,69,70,10,11,18,35,
%U 36,38,75,614,615,39,77,631,161914,161915
%N 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).
%C 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).
%F T(n,k) = T(n-1,k)+1 if 1 <= k <= A000108(n-1).
%e Triangle begins:
%e 0;
%e 1;
%e 2, 3;
%e 3, 4, 4, 7, 8;
%e 4, 5, 5, 8, 9, 5, 6, 8, 15, 16, 9, 17, 37, 38;
%e ...
%e 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.
%e (n,k) = (2,2), corresponding to the 2nd Dyck word on 2 pairs of brackets, "(())":
%e X
%e |
%e o H X X
%e | |/ |
%e R => R => R => R
%e T(2,2) = 1 + 1 + 1 = 3.
%e .
%e (n,k) = (3,4), corresponding to the 4th Dyck word on 3 pairs of brackets, "(()())":
%e H X H X
%e \ / \ /
%e o o o
%e \ \ /
%e R => R => R
%e T(3,4) = 1 + 2*T(2,2) = 7.
%e .
%e (n,k) = (4,10), corresponding to the 10th Dyck word on 4 pairs of brackets, "(()(()))":
%e X
%e |
%e o H X H H
%e | |/ | |
%e H--o H--o H--o o--X
%e \ \ \ /
%e R => R => R => R
%e T(4,10) = 1 + 1 + 2*T(3,4) = 16.
%Y Last elements on each row give A180368.
%Y Cf. A000108, A063171, A372592, A372593, A372595.
%K nonn,tabf
%O 0,3
%A _Pontus von Brömssen_, May 06 2024
|
