|
| |
|
|
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
|
|
|
|
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
|
The first row of A065625, i.e. a(n) = RotateNodeRight(1, n).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
