A065249 -id:A065249

The OEIS is supported by the many generous donors to the OEIS Foundation.

Search: a065249 -id:a065249

Displaying 1-5 of 5 results found.

page 1

A057114

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

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

KEYWORD

nonn

AUTHOR

Antti Karttunen, Aug 09 2000

STATUS

approved

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.

+10
10

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,1

COMMENTS

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.

LINKS

Table of n, a(n) for n=0..118.

A. Karttunen, How to generate A065249 and A065250

Index entries for sequences related to Stern's sequences

MAPLE

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

CROSSREFS

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.

KEYWORD

nonn,tabl

AUTHOR

Antti Karttunen, Nov 08 2001

STATUS

approved

A120705

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

+10
10

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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

LINKS

Table of n, a(n) for n=0..69.

A. Karttunen, Gatomorphisms <I>(With the complete Scheme source)</I>

N. J. A. Sloane, Stern-Brocot or Farey Tree

Index entries for signature-permutations induced by Catalan automorphisms

PROG

(Scheme function implementing this automorphism on list-structures:)

(define (gma120705! s) (cond ((pair? s) (gma074680! s) (gma120705! (car s)) (cond ((pair? (cdr s)) (gma120705! (cddr s)) (gma120706! (cadr s)))))) s)

CROSSREFS

Inverse of A120706. Cf. A074680.

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

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 28 2006

STATUS

approved

A065251

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

+10
5

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

LINKS

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

A. Karttunen, Conjecture regarding A065249 and A065251

FORMULA

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

MAPLE

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

MATHEMATICA

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

CROSSREFS

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

KEYWORD

sign

AUTHOR

Antti Karttunen, Oct 25 2001

STATUS

approved

A065250

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

+10
4

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

LINKS

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

Index entries for sequences related to Stern's sequences

Index entries for sequences that are permutations of the natural numbers

MAPLE

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

CROSSREFS

Cf. A057114, A065251. Inverse permutation A065249.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 25 2001

STATUS

approved

page 1

Search completed in 0.006 seconds