A065167 -id:A065167 - cp's OEIS frontend

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.

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;

A065626 Table of permutations of N, each row being a generator of the "rotation group" of infinite planar binary tree. Inverse generators are given in A065625.

Original entry on oeis.org

2, 4, 1, 1, 4, 1, 8, 3, 2, 1, 9, 8, 6, 2, 1, 5, 2, 4, 3, 2, 1, 3, 6, 5, 8, 3, 2, 1, 16, 7, 12, 5, 4, 3, 2, 1, 17, 16, 3, 6, 10, 4, 3, 2, 1, 18, 17, 8, 7, 6, 5, 4, 3, 2, 1, 19, 9, 9, 16, 7, 12, 5, 4, 3, 2, 1, 10, 5, 10, 4, 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 11, 10, 9, 8, 14, 6, 5, 4, 3, 2, 1, 6, 13, 24, 11, 20, 9, 8, 7, 6, 5, 4, 3, 2, 1, 7, 14, 25, 12, 5, 10, 9, 16, 7, 6, 5, 4, 3, 2

Offset: 0

Antti Karttunen, Nov 08 2001

The first row (rotate the top node left): A057115, 2nd row (rotate the top node's left child): A065628, 3rd row (rotate the top node's right child): A065630, 4th row: A065632, 5th row: A065634, 6th row: A065636, 7th row: A065638, 8th row: A065640. Maple procedure floor_log_2 given in A054429, for trinv, follow A065167.

[seq(RotateLeftTable(j),j=0..119)];
RotateLeftTable := n -> RotateNodeLeft(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 -> t0, t0... -> t00..., t1 -> t, t10... -> t01..., t11... -> t1... and leaves other x's intact.
RotateNodeLeft := 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); fi; if(0 = (floor(x/(2^(y-u-1))) mod 2)) then RETURN(x + (t * 2^(y-u))); fi; if(y = (u+1)) then RETURN((x-1)/2); fi; if(0 = (floor(x/(2^(y-u-2))) mod 2)) then RETURN(x - 2^(y-u-2)); fi; RETURN(x - ((t+1) * 2^(y-u-1))); end;

A065177 Table M(n,b) (columns: n >= 1, rows: b >= 0) gives the number of site swap juggling patterns with exact period n, using exactly b balls, where cyclic shifts are not counted as distinct.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 6, 3, 1, 0, 6, 15, 12, 4, 1, 0, 9, 42, 42, 20, 5, 1, 0, 18, 107, 156, 90, 30, 6, 1, 0, 30, 294, 554, 420, 165, 42, 7, 1, 0, 56, 780, 2028, 1910, 930, 273, 56, 8, 1, 0, 99, 2128, 7350, 8820, 5155, 1806, 420, 72, 9, 1, 0, 186, 5781, 26936

Offset: 0

Antti Karttunen, Oct 19 2001

			Upper left corner starts as:
  1, 0,  0,   0,    0,     0,     0, ...
  1, 1,  2,   3,    6,     9,    18, ...
  1, 2,  6,  15,   42,   107,   294, ...
  1, 3, 12,  42,  156,   554,  2028, ...
  1, 4, 20,  90,  420,  1910,  8820, ...
  1, 5, 30, 165,  930,  5155, 28830, ...
  1, 6, 42, 273, 1806, 11809, 77658, ...
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Juggling Information Service, Site Swap FAQs

Row 1: A059966, row 2: A065178, row 3: A065179, row 4: A065180.
Column 1: A002378, column 2: A059270.
Main diagonal gives A306173.
Cf. also A065167. trinv given at A054425.

[seq(DistSS_table(j),j=0..119)]; DistSS_table := (n) -> DistSS((((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1, (n-((trinv(n)*(trinv(n)-1))/2)));
with(numtheory); DistSS := proc(n,b) local d,s; s := 0; for d in divisors(n) do s := s+mobius(n/d)*((b+1)^d - b^d); od; RETURN(s/n); end;

trinv[n_] := Floor[(1 + Sqrt[8 n + 1])/2];
DistSS[n_, b_] := DivisorSum[n, MoebiusMu[n/#]*((b + 1)^# - b^#)&] /n;
a[n_] := DistSS[(((trinv[n] - 1)*(((1/2)*trinv[n]) + 1)) - n) + 1, (n - ((trinv[n]*(trinv[n] - 1))/2))];
Table[a[n], {n, 0, 119}] (* Jean-François Alcover, Mar 06 2016, adapted from Maple *)

Row n is the inverse Euler transform of j-> n^(j-1). - Alois P. Heinz, Jun 23 2018

A065166 Permutation t->t+3 of Z, folded to N.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Oct 19 2001

nonn

Corresponds to simple periodic asynchronic site swap pattern ...333333... (performing a three-ball cascade forever).

This permutation consists of just three infinite cycles.

Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers

Row 3 of A065167. Inverse permutation: A065170.

Let f: Z -> N be given by f(z) = 2z if z>0 else 2|z|+1, with inverse g(z) = z/2 if z even else (1-z)/2. Then a(n) = f(g(n)+3).

Empirical g.f.: x*(3*x^7-3*x^6+4*x^5-4*x^4+4*x^3-10*x^2+2*x+6) / ((x-1)^2*(x+1)). [Colin Barker, Feb 18 2013]

A065164 Permutation t->t+1 of Z, folded to N.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Oct 19 2001

Corresponds to simple periodic asynchronic site swap pattern ...111111... (tossing one ball from hand to hand forever).
This permutation consists of a single infinite cycle.
This is, starting at a(2) = 4, the same as the "increasing oscillating sequence" shown in Proposition 3.1, p.7 and plotted in the right of figure 1, of Vatter. The same paper, p.4, cites Comtet and uses without giving the A-number of A003319. Abstract: We prove that there are permutation classes (hereditary properties of permutations) of every growth rate (Stanley-Wilf limit) at least lambda = approx 2.48187, the unique real root of x^5-2x^4-2x^2-2x-1, thereby establishing a conjecture of Albert and Linton. - Jonathan Vos Post, Jul 18 2008

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 819.

Michael H. Albert, Robert Brignall, and Vincent Vatter, Large infinite antichains of permutations, arXiv:1212.3346 [math.CO], 2012.
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507-519.
Jay Pantone and Vincent Vatter, Growth rates of permutation classes: categorization up to the uncountability threshold, arXiv:1605.04289 [math.CO], 2016-2019.
Vincent Vatter, Permutation classes of every growth rate above 2.48188, arXiv:0807.2815 [math.CO], 2008-2009.
Vincent Vatter, Permutation classes, arXiv:1409.5159 [math.CO], 2014-2015.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).
Index entries for sequences that are permutations of the natural numbers.

Row 1 of A065167. Obtained by composing permutations A014681 and A065190. Inverse permutation: A065168.

ss1 := [seq(PerSS(n,1), n=1..120)]; PerSS := (n,c) -> Z2N(N2Z(n)+c);
N2Z := n -> ((-1)^n)*floor(n/2); Z2N := z -> 2*abs(z)+`if`((z < 1),1,0);

Join[{2}, LinearRecurrence[{1, 1, -1}, {4, 1, 6}, 100]] (* Amiram Eldar, Aug 08 2023 *)

Let f: Z -> N be given by f(z) = 2z if z>0 else 2|z|+1, with inverse g(z) = z/2 if z even else (1-z)/2. Then a(n) = f(g(n)+1).
a(n) = n + 2*(-1^n) for n > 1. - Frank Ellermann, Feb 12 2002
a(n) = 2*n-a(n-1)-1, n>2. - Vincenzo Librandi, Dec 07 2010, corrected by R. J. Mathar, Dec 07 2010
From Colin Barker, Feb 18 2013: (Start)
a(n) = a(n-1) + a(n-2) - a(n-3) for n>4.
G.f.: x*(3*x^3-5*x^2+2*x+2) / ((x-1)^2*(x+1)). (End)
Sum_{n>=1} (-1)^(n+1)/a(n) = log(2) + 1. - Amiram Eldar, Aug 08 2023

A065171 Permutation of Z, folded to N, corresponding to the site swap pattern ...26120123456... which ascends infinitely after t=0.

Original entry on oeis.org

1, 4, 2, 8, 3, 12, 6, 16, 5, 20, 10, 24, 7, 28, 14, 32, 9, 36, 18, 40, 11, 44, 22, 48, 13, 52, 26, 56, 15, 60, 30, 64, 17, 68, 34, 72, 19, 76, 38, 80, 21, 84, 42, 88, 23, 92, 46, 96, 25, 100, 50, 104, 27, 108, 54, 112, 29, 116, 58, 120, 31, 124, 62, 128, 33, 132, 66, 136, 35

Offset: 1

Antti Karttunen, Oct 19 2001

This permutation consists of one fixed point (at 0, mapped here to 1) and an infinite number of infinite cycles.

			G.f. = x + 4*x^2 + 2*x^3 + 8*x^4 + 3*x^5 + 12*x^6 + 6*x^7 + 16*x^8 + ...

Colin Barker, Table of n, a(n) for n = 1..1000
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers
Index entries for linear recurrences with constant coefficients, signature (0,0,0,2,0,0,0,-1).

Inverse permutation: A065172. A065173 gives the deltas p(t)-t, i.e., the associated site swap sequence. Cf. also A065167, A065174, A065260.

[seq(Z2N(InfRisingSS(N2Z(n))), n=1..120)]; InfRisingSS := z -> `if`((z < 0),`if`((0 = (z mod 2)),z/2,-z),2*z);
N2Z := n -> ((-1)^n)*floor(n/2); Z2N := z -> 2*abs(z)+`if`((z < 1),1,0);

Vec(x*(2*x^6+4*x^5+x^4+8*x^3+2*x^2+4*x+1)/((x-1)^2*(x+1)^2*(x^2+1)^2) + O(x^100)) \\ Colin Barker, Oct 29 2016

{a(n) = if( n%2, n\2+1, n*2)}; /* Michael Somos, Nov 06 2016 */

a(2*k+2) = 4*k+4, a(4*k+1) = 2*k+1, a(4*k+3) = 4*k+2. - Ralf Stephan, Jun 10 2005
G.f.: x*(2*x^6+4*x^5+x^4+8*x^3+2*x^2+4*x+1) / ((x-1)^2*(x+1)^2*(x^2+1)^2). - Colin Barker, Feb 18 2013
a(n) = 2*a(n-4)-a(n-8) for n>8. - Colin Barker, Oct 29 2016
a(n) = (11*n-1+(5*n+1)*(-1)^n+(n-3)*(1-(-1)^n)*(-1)^((2*n+3+(-1)^n)/4))/8. - Luce ETIENNE, Oct 20 2016

A065174 Permutation of Z, folded to N, corresponding to the site swap pattern ...242824202428242... (A065176).

Original entry on oeis.org

1, 6, 2, 12, 4, 10, 3, 24, 8, 14, 7, 20, 5, 18, 11, 48, 16, 22, 15, 28, 13, 26, 19, 40, 9, 30, 23, 36, 21, 34, 27, 96, 32, 38, 31, 44, 29, 42, 35, 56, 25, 46, 39, 52, 37, 50, 43, 80, 17, 54, 47, 60, 45, 58, 51, 72, 41, 62, 55, 68, 53, 66, 59, 192, 64, 70, 63, 76, 61, 74, 67, 88

Offset: 1

Antti Karttunen, Oct 19 2001

nonn

This permutation corresponds to the site swap pattern shown in the figure 7 of Buhler and Graham paper and consists of one fixed point (at 0, mapped here to 1) and infinite number of infinite cycles.

Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A065175. A065176 gives the deltas p(t)-t, i.e. the associated site swap sequence. Cf. also A065167, A065171.

[seq(Z2N(N2Z(n)+TZ2(abs(N2Z(n)))), n=1..120)]; TZ2 := proc(xx) local x,s; s := 1; x := xx; if(0 = x) then RETURN(0); fi; while(0 = (x mod 2)) do x := floor(x/2); s := s+1; od; RETURN(2^s); end;
N2Z := n -> ((-1)^n)*floor(n/2); Z2N := z -> 2*abs(z)+`if`((z < 1),1,0);

A065165 Permutation t->t+2 of Z, folded to N.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Oct 19 2001

Corresponds to simple periodic asynchronic site swap pattern ...222222... (holding a ball in each hand forever).

This permutation consists of just two infinite cycles.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507-519.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).
Index entries for sequences that are permutations of the natural numbers.

Row 2 of A065167. Inverse permutation: A065169.

CoefficientList[Series[(3 x^5 - 3 x^4 + 4 x^3 - 8 x^2 + 2 x + 4)/((x - 1)^2 (x + 1)), {x, 0, 100}], x] (* Vincenzo Librandi, Mar 08 2014 *)
LinearRecurrence[{1,1,-1},{4,6,2,8,1,10},80] (* Harvey P. Dale, May 09 2018 *)

Vec(x*(3*x^5-3*x^4+4*x^3-8*x^2+2*x+4)/((x-1)^2*(x+1))  + O(x^100)) \\ Colin Barker, Mar 07 2014

Let f: Z -> N be given by f(z) = 2z if z>0 else 2|z|+1, with inverse g(z) = z/2 if z even else (1-z)/2. Then a(n) = f(g(n)+2).
G.f.: x*(3*x^5-3*x^4+4*x^3-8*x^2+2*x+4) / ((x-1)^2*(x+1)). - Colin Barker, Feb 18 2013
a(n) = 4*(-1)^n+n for n>3. a(n) = a(n-1)+a(n-2)-a(n-3) for n>6. - Colin Barker, Mar 07 2014
Sum_{n>=1} (-1)^(n+1)/a(n) = log(2) + 3/2. - Amiram Eldar, Aug 08 2023

cp's OEIS Frontend

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

A065626 Table of permutations of N, each row being a generator of the "rotation group" of infinite planar binary tree. Inverse generators are given in A065625.

Views

Author

Keywords

Crossrefs

Programs

Maple

A065177 Table M(n,b) (columns: n >= 1, rows: b >= 0) gives the number of site swap juggling patterns with exact period n, using exactly b balls, where cyclic shifts are not counted as distinct.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A065166 Permutation t->t+3 of Z, folded to N.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A065164 Permutation t->t+1 of Z, folded to N.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A065171 Permutation of Z, folded to N, corresponding to the site swap pattern ...26120123456... which ascends infinitely after t=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Formula

A065174 Permutation of Z, folded to N, corresponding to the site swap pattern ...242824202428242... (A065176).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A065165 Permutation t->t+2 of Z, folded to N.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI