A038776 The sequence a[1] to a[ cat[n] ] is the permutation that converts forest[n] of depth-first planar planted binary trees into breadth-first representation.

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

Offset: 1

Author

Wouter Meeussen, May 04 2000

Keywords

• nonn

Examples

			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}}
		

Links

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

Crossrefs

Compare to the plot of A082364 and A072619.

Inverse of A070041. Cf. also A038774, A038775. If "expanded" produces A057117. Max cycle lengths: A057542.

Programs

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-(j-1))); 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 ], A014486%20*)%20Ordering%5BReverse%5Bwidthfirst%20/@%20b2d%20/@%20wood%5B6%5D%5D%5D%20(*%20_Wouter%20Meeussen">Integer ], {k, Depth[ # ]-1} ] }/.z->List ], -1 ] ] & @(bracket@d2b[ dectree ]); (* uses functions in A014486 *) Ordering[Reverse[widthfirst /@ b2d /@ wood[6]]] (* _Wouter Meeussen, Aug 19 2025 *)

Extensions

Additional comments from Antti Karttunen, Aug 11 2000