|
Search: id:A065625
|
|
|
| A065625 |
|
Table of permutations of N, each row being a generator of the "rotation group" of infinite planar binary tree. Inverse generators are given in A065626. |
|
+0
11
|
|
| 3, 1, 1, 7, 5, 1, 2, 3, 2, 1, 6, 2, 7, 2, 1, 14, 11, 4, 3, 2, 1, 15, 6, 5, 9, 3, 2, 1, 4, 7, 3, 5, 4, 3, 2, 1, 5, 4, 15, 6, 11, 4, 3, 2, 1, 12, 10, 8, 7, 6, 5, 4, 3, 2, 1, 13, 22, 9, 4, 7, 13, 5, 4, 3, 2, 1, 28, 23, 10, 19, 8, 7, 6, 5, 4, 3, 2, 1, 29, 12, 11, 10, 9, 8, 15, 6, 5, 4, 3, 2, 1, 30, 13, 6, 11, 5, 9, 8, 7, 6, 5, 4, 3, 2, 1, 31, 14, 14, 12, 23, 10, 9, 17, 7, 6, 5, 4, 3, 2
(list; table; graph; listen)
|
|
|
OFFSET
|
0,1
|
|
|
COMMENT
|
Consider the following infinite binary tree, where the nodes are numbered in breadth-first, left-to-right fashion from the top as:
.............................1............................
.............2...............................3............
.....4...............5...............6...............7....
.8.......9.......10.....11.......12.....13.......14.....15
etc., i.e. the node Y is a descendant of the node X, iff its binary expansion (the most significant bits) begin with the binary expansion of X.
In this table the n-th row is a permutation induced by the rotation of the node n right, and in the table A065626 the corresponding row gives the inverse of that permutation, induced by rotation of the node n left. Particular realizations of this tree are the Christoffel tree, and the Stern-Brocot tree (A007305/A007306), thus each such rotation, or composition of such rotations (e.g. A065249) induces a particular bijective function on rationals, and such functions form the "group A" of the order-preserving permutations of the rational numbers as defined by Cameron.
|
|
LINKS
|
A. Karttunen, How to generate A065249 and A065250
Index entries for sequences related to Stern's sequences
|
|
MAPLE
|
[seq(RotateRightTable(j), j=0..119)];
RotateRightTable := n -> RotateNodeRight(1+(n-((trinv(n)*(trinv(n)-1))/2)), (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1);
# Rewrites t-prefixed x's in the following way: t -> t1, t1... -> t11..., t0 -> t, t01... -> t10..., t00... -> t0..., and leaves other x's intact.
RotateNodeRight := proc(t, x) local u, y; u := floor_log_2(t)+1; y := floor_log_2(x)+1; if(y < u) then RETURN(x); fi; if(floor(x/(2^(y-u))) <> t) then RETURN(x); fi; if(x = t) then RETURN((2*x)+1); fi; if(1 = (floor(x/(2^(y-u-1))) mod 2)) then RETURN(x + (t * 2^(y-u)) + 2^(y-u)); fi; if(y = (u+1)) then RETURN(x/2); fi; if(1 = (floor(x/(2^(y-u-2))) mod 2)) then RETURN(x + 2^(y-u-2)); fi; RETURN(x - (t * 2^(y-u-1))); end;
|
|
CROSSREFS
|
The first row (rotate the top node right): A057114, 2nd row (rotate the top node's left child): A065627, 3rd row (rotate the top node's right child): A065629, 4th row: A065631, 5th row: A065633, 6th row: A065635, 7th row: A065637, 8th row: A065639. Maple procedure floor_log_2 given in A054429, for trinv, follow A065167.
Variant of the same idea: A065658.
Sequence in context: A118801 A080936 A094507 this_sequence A130749 A008277 A080417
Adjacent sequences: A065622 A065623 A065624 this_sequence A065626 A065627 A065628
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Antti Karttunen Nov 08 2001
|
|
|
Search completed in 0.003 seconds
|
