|
%I #17 Jul 22 2022 17:46:05
%S 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 35,39,15,16,18,19,17,22,25,20,21,34,38,29,30,31,65,66,69,70,68,78,79,
%U 83,84,82,74,75,77,81,106,107,111,112,110,125,126,131,132,130
%N 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 A. Karttunen, <a href="/A038776/b038776.txt">Table of n, a(n) for n = 1..1430</a>
%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/Nekomorphisms/gatomorf.htm">Gatomorphisms</a> (Includes the complete Scheme program for computing this sequence)
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e 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 [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 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 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 binwidth := n -> (`if`((0 = n),1,floor_log_2(n)+1));
%p 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;
%Y Compare to the plot of A082364 and A072619.
%Y Inverse of A070041. Cf. also A038774, A038775. If "expanded" produces A057117. Max cycle lengths: A057542.
%K nonn
%O 1,2
%A _Wouter Meeussen_, May 04 2000
%E Additional comments from Antti Karttunen, Aug 11 2000
|
