A372594 -id:A372594 - cp's OEIS frontend

A180368 Number of steps of the one-sided hydra process for a linear tree of length n.

0, 1, 3, 8, 38, 161915

Offset: 0

Vladimir Reshetnikov, Aug 31 2010

This process on trees is called Hydra in reference to the Hercules myth (killing the Hydra was the 2nd of the 12 labors of Hercules).
When you cut off a head (leaf node), the node that was its parent replicates together with a remaining subtree (unless the parent was the root node). The process ends when there is only the root node.
Given a linear hydra of length n, how many heads do you have to cut off if you always cut off the leftmost remaining head?
(Note that in the myth, the Hydra had 9 heads, and each head that was chopped off was replaced by two smaller ones.)

			Here is the sequence of hydra transformations for a(3) = 8.
Sequence of heights is     3,2,2,2,2,2,1,1,0.
Sequence of node counts is 4,4,5,5,4,3,3,2,1.
Sequence of head counts is 1,2,2,3,2,1,2,1,0.
x is the head that will be cut off at the next step:
x
|
o      x o      x o          o        o      x
|      |/       | |          |        |      |
o      o        o o      x o o      x o      o      x o      x
|      |        |/        \|/       |/       |      |/       |
o  =>  o    =>  o    =>    o    =>  o    =>  o  =>  o    =>  o  =>  o

Cf. A372101, A372421, A372478.

Last element in each row of A372594.

b:= proc(h) local f; f:= h[1];
       subsop(1=`if`(f=[], NULL,
                `if`(f[1]=[], (subsop(1=NULL, f))$2
                             , b(f))), h)
    end:
a:= proc(n) local i, t;
      [];
      for i to n do [%] od;
      for t from 0 while %<>[] do b(%) od; t
    end:
seq(a(n), n=0..5);  # Alois P. Heinz, Mar 31 2011

Edited by Olivier Gérard, Mar 28 2011

A372592 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.

Original entry on oeis.org

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, 13, 8, 10, 12, 16, 24, 32, 80, 448, 1114112, 9, 11, 13, 17, 25, 15, 19, 23, 31, 47, 63, 159, 895, 2228223, 79, 191, 447, 2303, 53247, 1114111, 45079976738815, 6065988000108893953800078394579416901568357495071628808248312306073599

Offset: 0

Pontus von Brömssen, May 06 2024

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.

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

			Triangle begins:
  0;
  1;
  2, 3;
  3, 4, 5, 7, 11;
  4, 5, 6, 8, 12, 7, 9, 11, 15, 23, 31, 79, 447, 1114111;
  ...
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.
.
        X
       /
  H   o         H   H       H   H       H   X      X
   \ /           \ /         \ /         \ /        \
    o             o--X        o H         o          o      X
    |             |           |/          |          |      |
    R       =>    R     =>    R--X  =>    R    =>    R  =>  R  =>  R
  T(4,10) = 1     +     1     +     2     +    6     +  12  +  1   = 23.

Last elements on each row give A372101.

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

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

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.

Original entry on oeis.org

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

Pontus von Brömssen, May 06 2024

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.

			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.

Last elements on each row give A372421.

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

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

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

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 5, 13, 37, 4, 5, 6, 14, 38, 7, 9, 37, 22539988369405

Offset: 0

Pontus von Brömssen, May 06 2024

T(4,9) = 41*2^39 - 3 = 22539988369405.

T(4,10) = (97*2^95+1)*2^(97*2^95-1) - 3 (1156727590779508264240712695467 digits).

			Triangle begins:
  0;
  1;
  2, 3;
  3, 4, 5, 13, 37;
  4, 5, 6, 14, 38, 7, 9, 37, 22539988369405, ...;
  ...

Last elements on each row give A372478.

Cf. A000108, A063171, A372592, A372593, A372594.

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

cp's OEIS Frontend

A180368 Number of steps of the one-sided hydra process for a linear tree of length n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Extensions

A372592 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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula