login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A057114 Permutation of N induced by the order-preserving permutation of the rational numbers (x -> x+1); positions in Stern-Brocot tree. 19
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, 59, 60, 61, 62, 63, 16, 17, 18, 19, 20, 21, 22, 23, 48, 49, 50, 51, 52, 53, 54, 55, 112, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

The "unbalancing operation" used here is what is usually called "rotation of binary trees" (e.g. in Lucas, Ruskey et al. article)

REFERENCES

Joan Lucas, Dominique Roelants van Baronaigien and Frank Ruskey, On Rotations and the Generation of Binary Trees, Journal of Algorithms, 15 (1993) 343-366.

LINKS

Table of n, a(n) for n=1..87.

A. Bogomolny, About the Stern-Brocot tree

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Index entries for sequences related to Stern's sequences

Index entries for sequences that are permutations of the natural numbers

FORMULA

a(n) = frac2position_in_whole_SB_tree (sbtree_perm_1_1_right (SternBrocotTreeNum(n) / SternBrocotTreeDen(n))).

EXAMPLE

Consider the following "extended" Stern-Brocot tree (on interval ]-inf,inf[):

....................................0/1

.................-1/1.................................1/1

......-2/1................-1/2...............1/2...............2/1

.-3/1......-3/2......-2/3......-1/3.....1/3.......2/3.....3/2.......3/1

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.

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.

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.

MAPLE

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)))))));

CROSSREFS

SternBrocotNum given in A007305, SternBrocotDen in A047679, frac2position_in_whole_SB_tree in A054424. Inverse permutation: A057115. Cf. also A065249 and A065250.

A065259(n) = A059893(A057114(A059893(n)))

The first row of A065625, i.e. a(n) = RotateNodeRight(1, n).

Sequence in context: A073874 A065287 A065263 * A235800 A065259 A065289

Adjacent sequences:  A057111 A057112 A057113 * A057115 A057116 A057117

KEYWORD

nonn

AUTHOR

Antti Karttunen, Aug 09 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 15 20:47 EST 2019. Contains 319184 sequences. (Running on oeis4.)