|
%I #8 May 01 2014 02:49:12
%S 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,
%T 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,
%U 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
%N 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.
%C Consider the following infinite binary tree, where the nodes are numbered in breadth-first, left-to-right fashion from the top as:
%C .............................1............................
%C .............2...............................3............
%C .....4...............5...............6...............7....
%C .8.......9.......10.....11.......12.....13.......14.....15
%C 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.
%C 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.
%H A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/stebrota.htm">How to generate A065249 and A065250</a>
%H <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%p [seq(RotateRightTable(j),j=0..119)];
%p RotateRightTable := n -> RotateNodeRight(1+(n-((trinv(n)*(trinv(n)-1))/2)),(((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1);
%p # 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.
%p 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;
%Y 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.
%Y Variant of the same idea: A065658.
%K nonn,tabl
%O 0,1
%A _Antti Karttunen_, Nov 08 2001
|
