A372593 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 left.

0, 1, 2, 3, 3, 4, 5, 6, 9, 4, 5, 6, 7, 10, 7, 8, 9, 10, 14, 18, 19, 25, 49, 5, 6, 7, 8, 11, 8, 9, 10, 11, 15, 19, 20, 26, 50, 9, 10, 11, 12, 16, 12, 13, 14, 15, 20, 25, 26, 33, 60, 30, 31, 32, 33, 41, 49, 50, 60, 110, 175, 176, 195, 330, 1230

Offset: 0

Author

Pontus von Brömssen, May 06 2024

Keywords

• nonn
• tabf

Comments

As in A372421, 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 left of all existing branches of that node.

For a given initial ordered tree T, the number of steps in the hydra game can be found by the following algorithm. The algorithm finds h(T,m0), the number of steps in a generalization of the game for an ordered tree T, with m0 new heads growing out at the first step (and, as before, increasing by one at each subsequent step). (So A(n,k) = h(T,1) if T is the k-th tree with n edges.)

1. If the root is the only node of T, return 0.

2. Set m = m0 and c = n - m*(m-1)/2, where n is the number of edges of T.

3. Delete the root from T. For each of the resulting tree components T' (from right to left), rooted at the node that was connected to the root of T:

a. Set m = m + h(T',m) + 1.

b. If T' is not the last tree, set c = c-m+1.

4. Return c + (m-1)*(m-2)/2.

Examples

			Triangle begins:
  0;
  1;
  2, 3;
  3, 4, 5, 6,  9;
  4, 5, 6, 7, 10, 7, 8, 9, 10, 14, 18, 19, 25, 49;
  ...
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". A number connected to the root represents that number of leaves, each connected to the root. 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 X       H X       X
  |/             \|/         \|        \
  o               o         H o         o         X
  |               |          \|         |         |
  R         =>    R    =>  H--R  =>  5--R  =>  9--R  =>  R
  A(4,10) = 1     +    1      +  1      +  1      +  10  = 14.
		

Crossrefs

Last elements on each row give A372421.

Cf. A000108, A063171, A372592, A372594, A372595.

Formula

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