|
Search: id:A038776
|
|
|
| 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. |
|
+0
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; listen)
|
|
|
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-(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 ], _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: A117606 A060736 A097292 this_sequence A118461 A011174 A123545
Adjacent sequences: A038773 A038774 A038775 this_sequence A038777 A038778 A038779
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Wouter Meeussen (wouter.meeussen(AT)pandora.be), May 04 2000
|
|
EXTENSIONS
|
Additional comments from Antti Karttunen, Aug 11 2000
|
|
|
Search completed in 0.002 seconds
|
