cp's OEIS Frontend

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.

%I A038776 #33 Aug 20 2025 03:48:56
%S A038776 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,
%T A038776 35,39,15,16,18,19,17,22,25,20,21,34,38,29,30,31,65,66,69,70,68,78,79,
%U A038776 83,84,82,74,75,77,81,106,107,111,112,110,125,126,131,132,130
%N 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.
%H A038776 Antti Karttunen, <a href="/A038776/b038776.txt">Table of n, a(n) for n = 1..1430</a>
%H A038776 Antti Karttunen, <a href="https://github.com/karttu/IntSeq/tree/master/src/Uncleaned/Catalania">Gatomorphisms</a> (Includes the complete Scheme program for computing this sequence).
%H A038776 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A038776 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}}
%p A038776 [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).
%p A038776 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;
%p A038776 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:
%p A038776 binwidth := n -> (`if`((0 = n),1,floor_log_2(n)+1));
%p A038776 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;
%t A038776 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 ]); (* uses functions in A014486 *) Ordering[Reverse[widthfirst /@ b2d /@ wood[6]]] (* _Wouter Meeussen_, Aug 19 2025 *)
%Y A038776 Compare to the plot of A082364 and A072619.
%Y A038776 Inverse of A070041. Cf. also A038774, A038775. If "expanded" produces A057117. Max cycle lengths: A057542.
%K A038776 nonn
%O A038776 1,2
%A A038776 _Wouter Meeussen_, May 04 2000
%E A038776 Additional comments from _Antti Karttunen_, Aug 11 2000