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
KEYWORD
nonn,more
AUTHOR
Vladimir Reshetnikov, Aug 31 2010
EXTENSIONS
Edited by Olivier Gérard, Mar 28 2011
STATUS
approved