A065249 -id:A065249 - 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.

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

Offset: 1

Antti Karttunen, Aug 09 2000

nonn

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

			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.

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

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

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

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

a(n) = frac2position_in_whole_SB_tree (sbtree_perm_1_1_right (SternBrocotTreeNum(n) / SternBrocotTreeDen(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.

Original entry on oeis.org

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, 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, 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

Offset: 0

Antti Karttunen, Nov 08 2001

Consider the following infinite binary tree, where the nodes are numbered in breadth-first, left-to-right fashion from the top as:
.............................1............................
.............2...............................3............
.....4...............5...............6...............7....
.8.......9.......10.....11.......12.....13.......14.....15
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.
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.

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.

Variant of the same idea: A065658.

[seq(RotateRightTable(j),j=0..119)];
RotateRightTable := n -> RotateNodeRight(1+(n-((trinv(n)*(trinv(n)-1))/2)),(((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1);
# 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.
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;

A120705 Permutation of natural numbers induced by the Catalan bijection gma120705 acting on the binary trees encoded by A014486/A063171.

Original entry on oeis.org

0, 1, 3, 2, 8, 7, 4, 5, 6, 22, 21, 17, 18, 20, 10, 9, 11, 13, 12, 14, 15, 19, 16, 64, 63, 58, 59, 62, 46, 45, 48, 50, 49, 54, 55, 61, 57, 27, 26, 23, 24, 25, 29, 28, 33, 34, 35, 30, 36, 32, 31, 38, 37, 39, 41, 40, 51, 52, 60, 56, 42, 43, 44, 47, 53, 196, 195, 189, 190, 194

Offset: 0

Antti Karttunen, Jun 28 2006

nonn

When the automorphisms A120705/A120705 act on the full Stern-Brocot tree (A007305/A047679), which is an infinite binary tree, they will move each fraction r to the position of 2*r (or r/2 respectively). See comments at A065249 and A065251. (Proof in preparation, to be published.)

A. Karttunen, Gatomorphisms (With the complete Scheme source)
N. J. A. Sloane, Stern-Brocot or Farey Tree
Index entries for signature-permutations induced by Catalan automorphisms

Inverse of A120706. Cf. A074680.

Number of cycles: A120707. Number of fixed-points: A019590. Max. cycle size: A120708. LCM of cycle sizes: A120709.

A065251 Simple quasi-periodic sequence consisting of the terms 1, 0 and -1.

Original entry on oeis.org

1, 1, 0, 1, 0, -1, 1, 1, 0, -1, 1, 0, -1, 1, 0, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0

Offset: 1

Antti Karttunen, Oct 25 2001

sign

A. Karttunen, Conjecture regarding A065249 and A065251

The same sequence modulo 3: A065252. Cf. A065249.

[seq(A065251(j),j=1..120)]; A065251 := n -> 1-((n-2^floor_log_2(n)) mod 3);

Table[1-Mod[n-2^Floor[Log[2,n]],3],{n,110}] (* Harvey P. Dale, Dec 25 2017 *)

a(n) = 1-((n-2^[log_2(n)]) mod 3)

A065250 Permutation of N induced by the order-preserving permutation of the positive rational numbers (x -> 2x), positions in Stern-Brocot tree.

Original entry on oeis.org

3, 1, 15, 5, 12, 7, 63, 2, 23, 48, 6, 29, 60, 31, 255, 9, 20, 11, 95, 192, 24, 51, 26, 14, 119, 240, 30, 125, 252, 127, 1023, 4, 39, 80, 10, 45, 92, 47, 383, 768, 96, 195, 98, 25, 207, 104, 13, 57, 116, 59, 479, 960, 120, 243, 122, 62, 503, 1008, 126, 509, 1020, 511

Offset: 1

Antti Karttunen, Oct 25 2001

nonn

Cf. A057114, A065251. Inverse permutation A065249.

[seq(A065250(j),j=1..120)]; A065250 := n -> frac2position_in_whole_SB_tree((SternBrocotTreeNum(n)/SternBrocotTreeDen(n))*2);

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A120705 Permutation of natural numbers induced by the Catalan bijection gma120705 acting on the binary trees encoded by A014486/A063171.

Views

Author

Keywords

Comments

Links

Crossrefs

A065251 Simple quasi-periodic sequence consisting of the terms 1, 0 and -1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A065250 Permutation of N induced by the order-preserving permutation of the positive rational numbers (x -> 2x), positions in Stern-Brocot tree.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple