A372595 -id:A372595 - cp's OEIS frontend

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.

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

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

Original entry on oeis.org

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

Pontus von Brömssen, May 06 2024

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

			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.

Last elements on each row give A180368.

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

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

A372478 Number of steps required to kill a Kirby-Paris hydra composed of a linear graph with n edges where, after removing the rightmost head at step s, s new subtrees sprout from the head's grandparent node (see comments).

Original entry on oeis.org

0, 1, 3, 37

Offset: 0

Paolo Xausa, May 02 2024

This is a variation of A372101 in which the hydra grows new subtrees instead of new heads. See Kirby and Paris (1982), p. 286, for a detailed explanation (with diagrams) of this process, for a generic hydra.
Similar to A372101, the initial configuration of this specific hydra is a path with n segments. The rightmost head is the next to be chopped off. When this happens at step s, s new replicas of the subtree above the removed head's grandparent node (which includes the segment connecting the head's parent and grandparent) sprout to the right of the grandparent node. If the chopped head has no grandparent, no subtrees are added.
As an example, here's how the following hypothetical portion of the hydra evolves, assuming we are at step 2 (H = head, o = node, X is chopped head, P = parent node, G = grandparent node):
.
  H   H        H   H H H H H
   \  |         \  | | | | |
    o o X        o o o o o o   2 new replicas (excluding the removed segment)
     \|/          \| |/  |/    of the subtree "above" (and including) the
      P    --->    o o   o     G-P segment grow at the right of node G
      |            |/   /
H--o--G      H--o--G----
      |            |
.
According to the Wikipedia article, a(4) >> Graham's number.
In their paper, Kirby and Paris prove that no matter what the starting configuration of the hydra is--as long as it's a finite tree--and no matter which head is chosen to be chopped off next, the hydra will eventually be defeated.
See A180368 for a variation in which only one new subtree grows after each chopping.

			In the following tree diagrams R is the root, o is a node and H is a head (leaf). Head chopping (leaf removal) is denoted by X.
For n = 2, the sequence of the 3 choppings is:
.
  H        X
   \        \
    o        o   H    H   X    X
     \        \ /      \ /      \
      R        R        R        R
.
For n = 3, the sequence of the 37 choppings is:
.
  H        X
   \        \
    o        o   H    H X H   H   H   H   X      H   H
     \        \ /      \| |  /     \  |  /        \  |
      o        o        o o o       o o o H H H    o o X X X X
       \        \        \|/         \|/ / / /      \|/ / / /
        R        R        R           R------        R------
.
  H   X          H              X
   \  |           \              \
    o o H (8) H    o   X (9) X    o   H  (18)  H   X   (19)  X
     \|/ ... /      \ / ... /      \ /  ...   /     \  ...  /
      R------        R------        R---------       ---R---
.

Laurie Kirby and Jeff Paris, Accessible Independence Results for Peano Arithmetic, Bulletin of The London Mathematical Society, 14, 1982, pp. 285-293.
PBS Infinite Series, Kill the Mathematical Hydra, YouTube video, 2017.
Wikipedia, Hydra game.

Cf. A180368, A372101, A372421.

Last element in each row of A372595.

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A372478 Number of steps required to kill a Kirby-Paris hydra composed of a linear graph with n edges where, after removing the rightmost head at step s, s new subtrees sprout from the head's grandparent node (see comments).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs