
COMMENTS

This process on trees is called Hydra in reference to Hercules myth (2nd work).
When you cut a head (leaf node), a node that was its parent replicates together with a remaining subtree (unless the parent was the root node). It ends when there is only the root node.
Given a linear hydra of length n, how many heads do you have to cut if you always cut the leftmost remaining head?
(Note that in the myth, Hydra had 9 heads and chopped heads were 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
