login
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.
4

%I #6 May 08 2024 14:56:29

%S 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,

%T 13,8,10,12,16,24,32,80,448,1114112,9,11,13,17,25,15,19,23,31,47,63,

%U 159,895,2228223,79,191,447,2303,53247,1114111,45079976738815,6065988000108893953800078394579416901568357495071628808248312306073599

%N 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.

%C 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.

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

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

%e Triangle begins:

%e 0;

%e 1;

%e 2, 3;

%e 3, 4, 5, 7, 11;

%e 4, 5, 6, 8, 12, 7, 9, 11, 15, 23, 31, 79, 447, 1114111;

%e ...

%e 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.

%e .

%e X

%e /

%e H o H H H H H X X

%e \ / \ / \ / \ / \

%e o o--X o H o o X

%e | | |/ | | |

%e R => R => R--X => R => R => R => R

%e T(4,10) = 1 + 1 + 2 + 6 + 12 + 1 = 23.

%Y Last elements on each row give A372101.

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

%K nonn,tabf

%O 0,3

%A _Pontus von Brömssen_, May 06 2024