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