

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.


10



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;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

Consider the following infinite binary tree, where the nodes are numbered in breadthfirst, lefttoright 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 nth 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 SternBrocot 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 orderpreserving permutations of the rational numbers as defined by Cameron.


LINKS

Table of n, a(n) for n=0..118.
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 tprefixed 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^(yu))) <> t) then RETURN(x); fi; if(x = t) then RETURN((2*x)+1); fi; if(1 = (floor(x/(2^(yu1))) mod 2)) then RETURN(x + (t * 2^(yu)) + 2^(yu)); fi; if(y = (u+1)) then RETURN(x/2); fi; if(1 = (floor(x/(2^(yu2))) mod 2)) then RETURN(x + 2^(yu2)); fi; RETURN(x  (t * 2^(yu1))); 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 * A287213 A284631 A154341
Adjacent sequences: A065622 A065623 A065624 * A065626 A065627 A065628


KEYWORD

nonn,tabl


AUTHOR

Antti Karttunen, Nov 08 2001


STATUS

approved



