cp's OEIS Frontend

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).

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