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,3

Links

Table of n, a(n) for n=0..71.

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)

Index entries for sequences that are permutations of the natural numbers

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;

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.

Sequence in context: A130349 A130354 A082356 * A130941 A082360 A130392

Adjacent sequences: A057114 A057115 A057116 * A057118 A057119 A057120

Keyword

nonn

Author

Antti Karttunen, Aug 11 2000

Status

approved