|
%I #8 Jun 10 2021 21:39:49
%S 7,25,1,31,22,1,1,3,2,1,223,10,247,2,1,15,94,4,3,2815,1,127,6,5,4,3,2,
%T 1,5,7,28,5,4,115,2,1,385,20479,127,6,94,4,3,2,1,13,175,8,7,6,5,4,3,2,
%U 1,1792,46,9,280,7,234881023,5,4,3,322,1,61,382,10,9,8,7,6,5,4,3,2,1
%N The table of permutations of N, each row induced by the rotation (to the right) of the n-th node in the infinite binary "decimal" fraction tree.
%C Consider the following infinite binary tree, where the nodes are numbered in breadth-first, left-to-right fashion from the top as in A065625 and then assigned the following rational values:
%C --------------------------------------(0.1)---------------------------------------
%C ----------------(0.01)-------------------------------------(0.11)-----------------
%C -----(0.001)--------------(0.011)---------------(0.101)--------------(0.111)------
%C (0.0001)-(0.0011)----(0.0101)-(0.0111)-----(0.1001)-(0.1011)-----(0.1101)-(0.1111)
%C i.e., the elements (1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, 1/16, 3/16, ..., of the Quasicyclic group Z+((2a+1)/(2^b)) for prime 2) listed here in their binary "decimal" fraction form. Subjecting this tree to any similar binary tree rotation as used in A065625 induces a permutation of the rationals in range ]0,1[ (i.e., including also the ones having infinite binary expansions, corresponding to infinite paths in above tree), which we then convert to permutations of N by taking the positions of the mapped values at the ]0,1[ side of the Stern-Brocot Tree (A007305/A007306). See example at A065670.
%H <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%p [seq(RotateBinFracRightTable(j),j=0..119)]; RotateBinFracRightTable := n -> RotateBinFracNodeRight(1+(n-((trinv(n)*(trinv(n)-1))/2)),(((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1);
%p RotateBinFracNodeRight := (t,n) -> frac2position_in_0_1_SB_tree(RotateBinFracNodeRight_x(t,SternBrocot0_1frac(n)));
%p RotateBinFracNodeRight_x := proc(t,x) local num,den; den := 2^(1+floor_log_2(t)); num := (2*(t-(den/2)))+1; if((x <= (num-1)/den) or (x >= (num+1)/den)) then RETURN(x); fi; if(x <= ((2*(num-1))+1)/(2*den)) then RETURN((2*(x - ((num-1)/den))) + ((num-1)/den)); fi; if(x < (num/den)) then RETURN(x + (1/(2*den))); fi; RETURN((num/den) + ((x-((num-1)/den))/2)); end;
%p SternBrocot0_1frac := proc(n) local m; m := n + 2^floor_log_2(n); SternBrocotTreeNum(m)/SternBrocotTreeDen(m); end;
%p frac2position_in_0_1_SB_tree := r -> RETURN(ReflectBinTreePermutation(cfrac2binexp(convert(1/r,confrac))));
%Y The first row (rotate the top node right): A065660, 2nd row (rotate the top node's left child): A065662, 3rd row (rotate the top node's right child): A065664, 4th row: A065666, 5th row: A065668, 6th row: A065670, 7th row: A065672. For the other needed Maple procedures follow A065625, A047679, A054424 and A054429. Cf. also A065674-A065676. Inverse permutations are given in A065659.
%Y Cf. also A065934-A065935.
%K nonn,tabl
%O 0,1
%A _Antti Karttunen_, Nov 22 2001
|
