cp's OEIS Frontend

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.

%I A372593 #5 May 08 2024 14:56:32
%S A372593 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,
%T A372593 10,11,15,19,20,26,50,9,10,11,12,16,12,13,14,15,20,25,26,33,60,30,31,
%U A372593 32,33,41,49,50,60,110,175,176,195,330,1230
%N 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.
%C A372593 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.
%C A372593 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.)
%C A372593   1. If the root is the only node of T, return 0.
%C A372593   2. Set m = m0 and c = n - m*(m-1)/2, where n is the number of edges of T.
%C A372593   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:
%C A372593     a. Set m = m + h(T',m) + 1.
%C A372593     b. If T' is not the last tree, set c = c-m+1.
%C A372593   4. Return c + (m-1)*(m-2)/2.
%F A372593 A(n,k) = A(n-1,k)+1 if 1 <= k <= A000108(n-1).
%e A372593 Triangle begins:
%e A372593   0;
%e A372593   1;
%e A372593   2, 3;
%e A372593   3, 4, 5, 6,  9;
%e A372593   4, 5, 6, 7, 10, 7, 8, 9, 10, 14, 18, 19, 25, 49;
%e A372593   ...
%e A372593 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.
%e A372593 .
%e A372593       X
%e A372593      /
%e A372593   H o           H H X       H X       X
%e A372593   |/             \|/         \|        \
%e A372593   o               o         H o         o         X
%e A372593   |               |          \|         |         |
%e A372593   R         =>    R    =>  H--R  =>  5--R  =>  9--R  =>  R
%e A372593   A(4,10) = 1     +    1      +  1      +  1      +  10  = 14.
%Y A372593 Last elements on each row give A372421.
%Y A372593 Cf. A000108, A063171, A372592, A372594, A372595.
%K A372593 nonn,tabf
%O A372593 0,3
%A A372593 _Pontus von Brömssen_, May 06 2024