|
| |
|
|
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.
|
|
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, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
|
|
|
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;
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Additional comments from Antti Karttunen, Aug 11 2000
|
|
|
STATUS
|
approved
|
| |
|
|
