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

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, 27, 25, 31, 32, 35, 36, 34, 28, 29, 30, 33, 45, 46, 49, 50, 48, 58, 59, 63, 64, 62, 54, 55, 57, 61, 37, 38, 40, 41, 39, 44, 47, 42, 43, 56, 60, 51, 52, 53, 65, 66, 68, 69, 67, 73, 74

Offset: 0

Author

Antti Karttunen, Aug 11 2000

Keywords

• nonn

Links

• A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Restriction of the automorphism A072088 to the plane binary trees.

Add one to each term and "overlay" each successive subpermutation of A000108[n] terms and one obtains A038776. Inverse permutation is A057118.

Programs

Maple

a(n) = CatalanRankGlobal(btbf2df(binrev(A014486[n]),0,1)/2)
Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES book, see A014486
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;
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;