login
A180368
Number of steps of the one-sided hydra process for a linear tree of length n.
4
0, 1, 3, 8, 38, 161915
OFFSET
0,3
COMMENTS
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.)
EXAMPLE
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
MAPLE
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
CROSSREFS
Last element in each row of A372594.
Sequence in context: A106558 A065914 A288759 * A108262 A034892 A072687
KEYWORD
nonn,more
AUTHOR
EXTENSIONS
Edited by Olivier Gérard, Mar 28 2011
STATUS
approved