OFFSET
0,3
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.
FORMULA
A(n,k) = A(n-1,k)+1 if 1 <= k <= A000108(n-1).
EXAMPLE
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
KEYWORD
nonn,tabf
AUTHOR
Pontus von Brömssen, May 06 2024
STATUS
approved