|
%I #22 Apr 24 2024 12:40:47
%S 0,1,3,8,38,161915
%N Number of steps of the one-sided hydra process for a linear tree of length n.
%C 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).
%C 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.
%C 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?
%C (Note that in the myth, the Hydra had 9 heads, and each head that was chopped off was replaced by two smaller ones.)
%e Here is the sequence of hydra transformations for a(3) = 8.
%e Sequence of heights is 3,2,2,2,2,2,1,1,0.
%e Sequence of node counts is 4,4,5,5,4,3,3,2,1.
%e Sequence of head counts is 1,2,2,3,2,1,2,1,0.
%e x is the head that will be cut off at the next step:
%e x
%e |
%e o x o x o o o x
%e | |/ | | | | |
%e o o o o x o o x o o x o x
%e | | |/ \|/ |/ | |/ |
%e o => o => o => o => o => o => o => o => o
%p b:= proc(h) local f; f:= h[1];
%p subsop(1=`if`(f=[], NULL,
%p `if`(f[1]=[], (subsop(1=NULL, f))$2
%p , b(f))), h)
%p end:
%p a:= proc(n) local i, t;
%p [];
%p for i to n do [%] od;
%p for t from 0 while %<>[] do b(%) od; t
%p end:
%p seq(a(n), n=0..5); # _Alois P. Heinz_, Mar 31 2011
%K nonn,more,changed
%O 0,3
%A _Vladimir Reshetnikov_, Aug 31 2010
%E Edited by _Olivier Gérard_, Mar 28 2011
|
