cp's OEIS Frontend

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.

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