cp's OEIS Frontend

A057114 Permutation of N induced by the order-preserving permutation of the rational numbers (x -> x+1); positions in Stern-Brocot tree.

%I A057114 #17 May 01 2014 02:48:24
%S A057114 3,1,7,2,6,14,15,4,5,12,13,28,29,30,31,8,9,10,11,24,25,26,27,56,57,58,
%T A057114 59,60,61,62,63,16,17,18,19,20,21,22,23,48,49,50,51,52,53,54,55,112,
%U A057114 113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,96,97,98,99,100,101,102,103
%N A057114 Permutation of N induced by the order-preserving permutation of the rational numbers (x -> x+1); positions in Stern-Brocot tree.
%C A057114 The "unbalancing operation" used here is what is usually called "rotation of binary trees" (e.g. in Lucas, Ruskey et al. article)
%D A057114 Joan Lucas, Dominique Roelants van Baronaigien and Frank Ruskey, On Rotations and the Generation of Binary Trees, Journal of Algorithms, 15 (1993) 343-366.
%H A057114 A. Bogomolny, <a href="http://www.cut-the-knot.org/blue/Stern.shtml">About the Stern-Brocot tree</a>
%H A057114 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H A057114 <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%H A057114 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A057114 a(n) = frac2position_in_whole_SB_tree (sbtree_perm_1_1_right (SternBrocotTreeNum(n) / SternBrocotTreeDen(n))).
%e A057114 Consider the following "extended" Stern-Brocot tree (on interval ]-inf,inf[):
%e A057114 ....................................0/1
%e A057114 .................-1/1.................................1/1
%e A057114 ......-2/1................-1/2...............1/2...............2/1
%e A057114 .-3/1......-3/2......-2/3......-1/3.....1/3.......2/3.....3/2.......3/1
%e A057114 Enumerate the fractions breadth-first (0/1 = 1, -1/1 = 2, 1/1 = 3, -2/1 = 4, -1/2 = 5, etc.) then use this sequence to pick third, first, 7th, 2nd, etc. fractions. We get a bijection (0/1 -> 1/1, -1/1 -> 0/1, 1/1 -> 2/1, -2/1 -> -1/1, -1/2 -> 1/2, etc.) which is the function x -> x+1.
%e A057114 In other words, we cut the edge between 1/1 and 1/2, make 1/1 the new root and create a new edge between 0/1 and 1/2 to get an "unbalanced" Stern-Brocot tree. If we instead make a similar change to subtree 1/1 (cut {2/1,3/2}, create {1/1,3/2} and make 2/1 the new root of the positive side, leaving the negative side as it is), we get the function given in Maple procedure sbtree_perm_1_1_right.
%e A057114 Both mappings belong to Cameron's group "A" of permutations of the rational numbers which preserve their linear order and by applying such unbalancing operations successively (possibly infinitely many times) to the "extended" Stern-Brocot tree given above, the whole group "A" can be generated.
%p A057114 sbtree_perm_1_1_right := x -> (`if`((x <= 0),x,(`if`((x < (1/2)),(x/(1-x)),(`if`((x < 1),(3-(1/x)),(x+1)))))));
%Y A057114 SternBrocotNum given in A007305, SternBrocotDen in A047679, frac2position_in_whole_SB_tree in A054424. Inverse permutation: A057115. Cf. also A065249 and A065250.
%Y A057114 A065259(n) = A059893(A057114(A059893(n)))
%Y A057114 The first row of A065625, i.e. a(n) = RotateNodeRight(1, n).
%K A057114 nonn
%O A057114 1,1
%A A057114 _Antti Karttunen_, Aug 09 2000