A372592 Irregular triangle read by rows, where the n-th row gives the number of steps in the hydra game 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) and new heads are grown to the right.

0, 1, 2, 3, 3, 4, 5, 7, 11, 4, 5, 6, 8, 12, 7, 9, 11, 15, 23, 31, 79, 447, 1114111, 5, 6, 7, 9, 13, 8, 10, 12, 16, 24, 32, 80, 448, 1114112, 9, 11, 13, 17, 25, 15, 19, 23, 31, 47, 63, 159, 895, 2228223, 79, 191, 447, 2303, 53247, 1114111, 45079976738815, 6065988000108893953800078394579416901568357495071628808248312306073599

Offset: 0

Author

Pontus von Brömssen, May 06 2024

Keywords

• nonn
• tabf

Comments

As in A372101, the rightmost head (leaf) is always chopped off, and after the m-th head is chopped off (if it is not directly connected to the root) m new heads grow from the node two levels closer to the root from the head chopped off (its grandparent) to the right of all existing branches of that node.

T(5,37) = 20472...84351 (167697 digits). The corresponding initial tree is represented by the bracket string "((()(())))" (the 37th Dyck word on 5 pairs of brackets).

Examples

			Triangle begins:
  0;
  1;
  2, 3;
  3, 4, 5, 7, 11;
  4, 5, 6, 8, 12, 7, 9, 11, 15, 23, 31, 79, 447, 1114111;
  ...
For n = 4, k = 10, the hydra game for the initial tree corresponding to the bracket string "(()(()))" (the 10th Dyck word on 4 pairs of brackets) is shown below. 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.
.
        X
       /
  H   o         H   H       H   H       H   X      X
   \ /           \ /         \ /         \ /        \
    o             o--X        o H         o          o      X
    |             |           |/          |          |      |
    R       =>    R     =>    R--X  =>    R    =>    R  =>  R  =>  R
  T(4,10) = 1     +     1     +     2     +    6     +  12  +  1   = 23.
		

Crossrefs

Last elements on each row give A372101.

Cf. A000108, A063171, A372593, A372594, A372595.

Formula

T(n,k) = T(n-1,k)+1 if 1 <= k <= A000108(n-1).