

A038776


The sequence a[1] to a[ cat[n] ] is the permutation that converts forest[n] of depthfirst planar planted binary trees into breadthfirst representation.


11



1, 2, 4, 5, 3, 9, 10, 13, 14, 12, 6, 7, 8, 11, 23, 24, 27, 28, 26, 36, 37, 41, 42, 40, 32, 33, 35, 39, 15, 16, 18, 19, 17, 22, 25, 20, 21, 34, 38, 29, 30, 31, 65, 66, 69, 70, 68, 78, 79, 83, 84, 82, 74, 75, 77, 81, 106, 107, 111, 112, 110, 125, 126, 131, 132, 130
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS

A. Karttunen, Table of n, a(n) for n = 1..1430
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers


EXAMPLE

tree ( 1 (100) (10 ) ) becomes (1) (11)(00 0 ) thus (1 (1(100) 0) ) and is permuted from position 3 in forest[3] to position 5 by permutation {1,2,4,5,3}={{1},{2},{4,5,3}}


MAPLE

[seq(CatalanRank(inf, (btbf2df(binrev(CatalanUnrank(inf, j)), 0, 1)/2))+1, j=0..(binomial(2*inf, inf)/(inf+1))1)]; (In practice, use a value like 6 instead of infinity).
btbf2df := proc(nn, i, r) local n, j, c, x, y, w; n := nn; if(0 = (n mod 2)) then RETURN(0); fi; c := i; for j from 1 to r do c := c + (n mod 2); n := floor(n/2); od; w := 2*c; c := 0; for j from 1 to (2*i) do c := c + (n mod 2); n := floor(n/2); od; x := btbf2df(n, c, (w(j1))); y := btbf2df(floor(n/2), c+(n mod 2), (w(j))); RETURN((2^(binwidth(x)+binwidth(y))) + (x * (2^(binwidth(y)))) + y); end;
floor_log_2 := proc(n) local nn, i: nn := n; for i from 1 to n do if(0 = nn) then RETURN(i); fi: nn := floor(nn/2); od: end:
binwidth := n > (`if`((0 = n), 1, floor_log_2(n)+1));
binrev := proc(nn) local n, z; n := nn; z := 0; while(n <> 0) do z := 2*z + (n mod 2); n := floor(n/2); od; RETURN(z); end;


MATHEMATICA

bracket[ tree_ ] := (Flatten[ {tree, 0} ]/. 0>{0})//.{1, z___, 1, a_List, b_List, y___}:>{1, z, {1, a, b}, y}; widthfirst[ dectree_ ] := b2d[ Drop[ Flatten[ {Table[ Cases[ Level[ #, {k}, z ], _Integer ], {k, Depth[ # ]1} ] }/.z>List ], 1 ] ] & @(bracket@d2b[ dectree ]); ToCycles[ Ordering[ widthfirst/@wood[ 9 ] ] ]; compare functions in A014486.


CROSSREFS

Compare to the plot of A082364 and A072619.
Inverse of A070041. Cf. also A038774, A038775. If "expanded" produces A057117. Max cycle lengths: A057542.
Sequence in context: A060736 A097292 A269780 * A210863 A245816 A118461
Adjacent sequences: A038773 A038774 A038775 * A038777 A038778 A038779


KEYWORD

nonn


AUTHOR

Wouter Meeussen, May 04 2000


EXTENSIONS

Additional comments from Antti Karttunen, Aug 11 2000


STATUS

approved



