cp's OEIS Frontend

A057117 Permutation of nonnegative integers obtained by mapping each forest of A000108[n] rooted binary plane trees from breadth-first to depth-first encoding.

%I A057117 #5 May 01 2014 02:48:24
%S A057117 0,1,2,3,4,5,7,8,6,9,10,12,13,11,17,18,21,22,20,14,15,16,19,23,24,26,
%T A057117 27,25,31,32,35,36,34,28,29,30,33,45,46,49,50,48,58,59,63,64,62,54,55,
%U A057117 57,61,37,38,40,41,39,44,47,42,43,56,60,51,52,53,65,66,68,69,67,73,74
%N A057117 Permutation of nonnegative integers obtained by mapping each forest of A000108[n] rooted binary plane trees from breadth-first to depth-first encoding.
%H A057117 A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/Nekomorphisms/gatomorf.htm">Gatomorphisms</a> (Includes the complete Scheme program for computing this sequence)
%H A057117 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%p A057117 a(n) = CatalanRankGlobal(btbf2df(binrev(A014486[n]),0,1)/2)
%p A057117 Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES book, see A014486
%p A057117 CatalanRank := proc(n,aa) local x,y,lo,a; a := binrev(aa); y := 0; lo := 0; for x from 1 to (2*n)-1 do lo := lo + (1-(a mod 2))*Mn(n,x,y+1); y := y - ((-1)^a); a := floor(a/2); od; RETURN((binomial(2*n,n)/(n+1))-(lo+1)); end;
%p A057117 CatalanRankGlobal := proc(a) local n; n := floor(binwidth(a)/2); RETURN(add((binomial(2*j,j)/(j+1)),j=0..(n-1))+CatalanRank(n,a)); end;
%Y A057117 Restriction of the automorphism A072088 to the plane binary trees.
%Y A057117 Add one to each term and "overlay" each successive subpermutation of A000108[n] terms and one obtains A038776. Inverse permutation is A057118.
%K A057117 nonn
%O A057117 0,3
%A A057117 _Antti Karttunen_, Aug 11 2000