A372594 Irregular triangle read by rows, where the n-th row gives the number of steps in the hydra game (the version described in A180368) 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).

0, 1, 2, 3, 3, 4, 4, 7, 8, 4, 5, 5, 8, 9, 5, 6, 8, 15, 16, 9, 17, 37, 38, 5, 6, 6, 9, 10, 6, 7, 9, 16, 17, 10, 18, 38, 39, 6, 7, 7, 10, 11, 9, 10, 16, 31, 32, 17, 33, 69, 70, 10, 11, 18, 35, 36, 38, 75, 614, 615, 39, 77, 631, 161914, 161915

Offset

0,3

Comments

Here, in contrast to A180368, the rightmost head is always chopped off. Equivalently, chop off the leftmost head but interpret the Dyck words as describing the trees from the right to the left (or sort the Dyck words colexicographically).

Links

Table of n, a(n) for n=0..64.

Formula

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

Example

Triangle begins:
  0;
  1;
  2, 3;
  3, 4, 4, 7, 8;
  4, 5, 5, 8, 9, 5, 6, 8, 15, 16, 9, 17, 37, 38;
  ...
In the examples below, the hydra games for some initial trees are shown. 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.
  (n,k) = (2,2), corresponding to the 2nd Dyck word on 2 pairs of brackets, "(())":
    X
    |
    o          H X      X
    |          |/       |
    R      =>  R    =>  R  =>  R
  T(2,2) = 1   +    1   +  1   = 3.
.
  (n,k) = (3,4), corresponding to the 4th Dyck word on 3 pairs of brackets, "(()())":
  H   X        H       X
   \ /          \     /
    o            o   o
     \            \ /
      R    =>      R      =>  R
  T(3,4) = 1       + 2*T(2,2) = 7.
.
  (n,k) = (4,10), corresponding to the 10th Dyck word on 4 pairs of brackets, "(()(()))":
      X
      |
      o            H X         H   H
      |            |/          |   |
   H--o         H--o        H--o   o--X
       \            \           \ /
        R   =>       R  =>       R       =>  R
  T(4,10) = 1        +  1        +  2*T(3,4) = 16.

Crossrefs

Last elements on each row give A180368.

Cf. A000108, A063171, A372592, A372593, A372595.

Sequence in context: A095916 A130121 A007898 * A367009 A110533 A131282

Adjacent sequences: A372591 A372592 A372593 * A372595 A372596 A372597

Keyword

nonn,tabf

Author

Pontus von Brömssen, May 06 2024

Status

approved