A165962 -id:A165962 - cp's OEIS frontend

A165961 Number of circular permutations of length n without 3-sequences.

1, 5, 20, 102, 627, 4461, 36155, 328849, 3317272, 36757822, 443846693, 5800991345, 81593004021, 1228906816941, 19733699436636, 336554404751966, 6075478765948135, 115734570482611885, 2320148441078578447, 48827637296350480457, 1076313671861962141616

Offset: 3

Isaac Lambert, Oct 01 2009

nonn

Circular permutations are permutations whose indices are from the ring of integers modulo n. 3-sequences are of the form i,i+1,i+2. Sequence gives number of permutations of [n] starting with 1 and having no 3-sequences.

a(n) is also the number of permutations of length n-1 without consecutive fixed points (cf. A180187). - David Scambler, Mar 27 2011

			For n=4 the a(4)=5 solutions are (0,1,3,2), (0,2,1,3), (0,2,3,1), (0,3,1,2) and (0,3,2,1).

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012. - From N. J. A. Sloane, Sep 15 2012 [broken link]

Michael De Vlieger, Table of n, a(n) for n = 3..450
Wayne M. Dymacek and Isaac Lambert, Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011), Article 11.1.6.
Kyle Parsons, Arithmetic progressions in permutations, Thesis, 2011.

Cf. A002628, A165960, A165962.
Cf. A000166, A180186, - Emeric Deutsch, Sep 07 2010
A column of A216718. - N. J. A. Sloane, Sep 15 2012

d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-k, k)*d[n-k-1], k = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 3 .. 23); # Emeric Deutsch, Sep 07 2010

a[n_] := Sum[Binomial[n-k, k] Subfactorial[n-k-1], {k, 0, n/2}];
a /@ Range[3, 21] (* Jean-François Alcover, Oct 29 2019 *)

Let b(n) be the sequence A002628. Then for n > 5, this sequence satisfies a(n) = b(n-1) - b(n-3) + a(n-3).

a(n) = Sum_{k=0..n/2} binomial(n-k,k)*d(n-k-1), where d(j)=A000166(j) are the derangement numbers. - Emeric Deutsch, Sep 07 2010

More terms from Emeric Deutsch, Sep 07 2010

Edited by N. J. A. Sloane, Apr 04 2011

A002628 Number of permutations of length n without 3-sequences.

Original entry on oeis.org

1, 1, 2, 5, 21, 106, 643, 4547, 36696, 332769, 3349507, 37054436, 446867351, 5834728509, 82003113550, 1234297698757, 19809901558841, 337707109446702, 6094059760690035, 116052543892621951, 2325905946434516516, 48937614361477154273, 1078523843237914046247

Offset: 0

N. J. A. Sloane

nonn

a(n) = sum of row n of A180185. - Emeric Deutsch, Sep 06 2010

			a(4) = 21 because only 1234, 2341, and 4123 contain 3-sequences. - _Emeric Deutsch_, Sep 06 2010

Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), number 1, 297-305.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..450
D. M. Jackson and R. C. Read, A note on permutations without runs of given length, Aequationes Math. 17 (1978), no. 2-3, 336-343.
J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.

Column k=0 of A047921.
Cf. A165960, A165961, A165962. - Isaac Lambert, Oct 07 2009
Cf. A000166, A180185. - Emeric Deutsch, Sep 06 2010

seq(coeff(convert(series(add(m!*((t-t^3)/(1-t^3))^m,m=0..50),t,50), polynom), t,n),n=0..25); # Pab Ter, Nov 06 2005
d[-1]:= 0: for n from 0 to 51 do d[n] := n*d[n-1]+(-1)^n end do: a:= proc(n) add(binomial(n-k, k)*(d[n-k]+d[n-k-1]), k = 0..floor((1/2)*n)) end proc: seq(a(n), n = 0..25); # Emeric Deutsch, Sep 06 2010
# third Maple program:
a:= proc(n) option remember; `if`(n<5,
      [1$2, 2, 5, 21][n+1], (n-3)*a(n-1)+(3*n-6)*a(n-2)+
      (4*n-12)*a(n-3)+(3*n-12)*a(n-4)+(n-5)*a(n-5))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jul 21 2019

d[0] = 1; d[n_] := d[n] = n d[n - 1] + (-1)^n;
T[n_, k_] := If[n == 0 && k == 0, 1, If[k <= n/2, Binomial[n - k, k] d[n + 1 - k]/(n - k), 0]];
a[n_] := Sum[T[n, k], {k, 0, Quotient[n, 2]}];
a /@ Range[0, 25] (* Jean-François Alcover, May 23 2020 *)

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k)*(d(n-k) + d(n-k-1)) for n>0, where d(j) = A000166(j) are the derangement numbers. - Emeric Deutsch, Sep 06 2010

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005

a(0)=1 prepended by Alois P. Heinz, Jul 21 2019

A174075 Number of circular permutations of length n without modular consecutive triples i,i+2,i+4.

Original entry on oeis.org

1, 6, 18, 93, 600, 4320, 35168, 321630, 3257109, 36199458, 438126986, 5736774869, 80808984725, 1218563192160, 19587031966352, 334329804180135, 6039535339644630, 115118210695441900, 2308967760171049528, 48613722701440862328, 1072008447320752890459

Offset: 3

Isaac Lambert, Mar 06 2010

nonn

Circular permutations are permutations whose indices are from the ring of integers modulo n.

			Since a(5)=18, there are (5-1)!-18=4 circular permutations with modular consecutive triples i,i+2,i+4 in all circular permutations of length 5. These are exactly (0,2,4,1,3), (0,2,4,3,1), (0,4,2,1,3), and (0,3,2,4,1). Note some have more than one modular progression.

Max Alekseyev, Table of n, a(n) for n = 3..100
Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, 2012.

Column 1 of A216726.

Cf. A165962, A174072, A174073, A174074.

f[i_,n_,k_]:=If[i==0 && k==0,1,If[i==n && n==k,1,Binomial[k-1,k-i]*Binomial[n-k-1,k-i-1] + 2*Binomial[k-1,k-i-1]*Binomial[n-k-1,k-i-1]+Binomial[k-1,k-i-1]*Binomial[n-k-1,k-i]]];
w1[i_,n_,k_]:=If[n-2k+i<0,0,If[n-2k+i==0,1,(n-2k+i-1)!]];
a[n_,k_]:=Sum[f[i,n,k]*w1[i,n,k],{i,0,k}];
A165962[n_]:=(n-1)!+Sum[(-1)^k*a[n,k],{k,1,n}];
b[n_,k_]:=Sum[Sum[Sum[f[j,n/2,p]*f[i-j,n/2,k-p]*w2[i,j,n,k,p],{p,0,k}],{j,0,i}],{i,0,k-1}];
w2[i_,j_,n_,k_,p_]:=If[n/2-2p+j<=0 || n/2-2(k-p)+(i-j)<=0,0,(n-2k+i-1)!];
A216727[n_?EvenQ]:=(n-1)!+Sum[(-1)^k*b[n,k],{k,1,n}];
A216727[n_?OddQ]:=A165962[n];
Table[A216727[n],{n,3,23}] (* David Scambler, Sep 18 2012 *)

a(n) = A165962(n) for odd n.

A235943 Number a(n,k) of positions (cyclic permutations) of circular permutations of [n] with exactly k (unspecified) increasing or decreasing modular runs (3-sequences), with clockwise and counterclockwise traversals counted as distinct; triangle a(n,k) read by rows, 0<=k<=n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 16, 0, 0, 0, 8, 60, 50, 0, 0, 0, 10, 456, 144, 108, 0, 0, 0, 12, 3458, 1078, 294, 196, 0, 0, 0, 14, 29296, 7936, 2240, 512, 320, 0, 0, 0, 16, 275166, 66096, 16200, 4104, 810, 486, 0, 0, 0, 18, 2843980, 611200, 135600, 29200, 6900, 1200, 700, 0, 0, 0, 20

Offset: 0

Paul J. Campbell, Jan 20 2014, with Joe Marasco and Ashish Vikram

Arrangements that differ in the direction in which the cycle is traversed count as different.

Paul J. Campbell, Circular permutations with exactly one modular run (3-sequence), submitted to Journal of Integer Sequences

Paul J. Campbell, Rows n = 0..13, flattened
Paul J. Campbell, Table of rows n = 0..13 of A235943
Wayne M. Dymáček and Isaac Lambert, Circular permutations avoiding runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011) Article 11.1.6.

Cf. A165961, A165964, A165962, A078628, A078673.

Cf. A235937, A235938, A235939, A235940, A235941, A235942.

A235937 Number of circular permutations with exactly one specified increasing or decreasing modular run (3-sequence), with clockwise and counterclockwise traversals not counted as distinct.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 11, 62, 408, 3056, 25821, 242802, 2517303, 28540102, 351383192, 4669815008, 66640974977, 1016522211474, 16507095990251, 284343231536742, 5178919228252440

Offset: 1

Paul J. Campbell, Jan 20 2014, with Joe Marasco and Ashish Vikram

nonn

Arrangements that differ only in the direction in which the cycle is traversed do not count as different.

This sequence is the same as for straight permutations of {0,1,...,n} that begin with {0,1} and end with {n-1,n} but have no increasing or decreasing 3-sequence, viz., the sequence b(0,1...n-2,n-1) in Dymáček and Lambert.

			With specified sequence 123:
a(5) = 1: 12354.
a(6) = 2: 123564, 123645.
a(7) = 11: 1235476, 1235746, 1235764, 1236475, 1236574, 1236745, 1236754, 1237465, 1237546, 1237564, 1237645.

Paul J. Campbell, Circular permutations with exactly one modular run (3-sequence), submitted to Journal of Integer Sequences

Wayne M. Dymáček and Isaac Lambert, Circular permutations avoiding runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011) Article 11.1.6.

Cf. A165961, A165964, A165962, A078628, A078673.

Cf. A235938, A235939, A235940, A235941, A235942, A235943.

a(20)-a(21) from Alois P. Heinz, Jan 24 2014

Obsolete b-file deleted by N. J. A. Sloane, Jan 05 2019

A235938 Number of circular permutations with exactly one specified increasing or decreasing modular run (3-sequence), with clockwise and counterclockwise traversals counted as distinct.

Original entry on oeis.org

0, 0, 0, 0, 2, 4, 22, 124, 816, 6112, 51642, 485604, 5034606, 57080204, 702766384, 9339630016, 133281949954, 2033044422948, 33014191980502, 568686463073484, 10357838456504880

Offset: 1

Paul J. Campbell, Jan 20 2014, with Joe Marasco and Ashish Vikram

nonn

			With specified sequence 123:
a(5) = 2: 12354, 32154.
a(6) = 4: 123564, 321564, 123645, 321546.

Paul J. Campbell, Circular permutations with exactly one modular run (3-sequence), submitted to Journal of Integer Sequences

Wayne M. Dymáček and Isaac Lambert, Circular permutations avoiding runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011) Article 11.1.6.

Cf. A165961, A165964, A165962, A078628, A078673.

Cf. A235937, A235939, A235940, A235941, A235942, A235943.

a(n) = 2*A235937(n).

a(20)-a(21) from Alois P. Heinz, Jan 24 2014

Obsolete b-file deleted by N. J. A. Sloane, Jan 05 2019

A235939 Number of circular permutations with exactly one (unspecified) increasing or decreasing modular 3-sequence, with clockwise and counterclockwise traversals not counted as distinct.

Original entry on oeis.org

0, 0, 0, 0, 5, 12, 77, 496, 3672, 30560, 284031, 2913624, 32724939, 399561428, 5270747880, 74717040128, 1132896574609, 18297399806532, 313634823814769, 5686864630734840, 108757303793301240

Offset: 1

Paul J. Campbell, Jan 20 2014, with Joe Marasco and Ashish Vikram

nonn

Arrangements that differ only in the direction in which the cycle is traversed do not count as different.

			a(5) = 5: 12354, 23415, 34521, 45132, 51243.

Paul J. Campbell, Circular permutations with exactly one modular run (3-sequence), submitted to Journal of Integer Sequences

Wayne M. Dymáček and Isaac Lambert, Circular permutations avoiding runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011) Article 11.1.6.

Cf. A165961, A165964, A165962, A078628, A078673.

Cf. A235937, A235938, A235940, A235941, A235942, A235943.

a(n) = n*A235937(n).

a(20)-a(21) from Alois P. Heinz, Jan 24 2014

Obsolete b-file deleted by N. J. A. Sloane, Jan 05 2019

A235940 Number of circular permutations with exactly one (unspecified) increasing or decreasing modular 3-sequence, with clockwise and counterclockwise traversals counted as distinct.

Original entry on oeis.org

0, 0, 0, 0, 10, 24, 154, 992, 7344, 61120, 568062, 5827248, 65449878, 799122856, 10541495760, 149434080256, 2265793149218, 36594799613064, 627269647629538, 11373729261469680, 217514607586602480

Offset: 1

Paul J. Campbell, Jan 20 2014, with Joe Marasco and Ashish Vikram

Paul J. Campbell, Circular permutations with exactly one modular run (3-sequence), submitted to Journal of Integer Sequences.

Wayne M. Dymáček and Isaac Lambert, Circular permutations avoiding runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011), Article 11.1.6.

Cf. A165961, A165964, A165962, A078628, A078673.

Cf. A235937, A235938, A235939, A235941, A235942, A235943.

a(n) = 2n*A235937(n).
a(n) = n*A235938(n).
a(n) = 2*A235939(n).

a(20)-a(21) added using the data at A235939 by Amiram Eldar, May 06 2024

A235941 Positions (cyclic permutations) of circular permutations with exactly one (unspecified) increasing or decreasing modular 3-sequence, with clockwise and counterclockwise traversals not counted as distinct.

Original entry on oeis.org

0, 0, 0, 0, 25, 72, 539, 3968, 33048, 305600, 3124341, 34963488, 425424207, 5593859992, 79061218200, 1195472642048, 19259241768353, 329353196517576, 5959061652480611, 113737292614696800, 2283903379659326040

Offset: 1

Paul J. Campbell, Jan 20 2014, with Joe Marasco and Ashish Vikram

nonn

Paul J. Campbell, Circular permutations with exactly one modular run (3-sequence), submitted to Journal of Integer Sequences

Wayne M. Dymáček and Isaac Lambert, Circular permutations avoiding runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011) Article 11.1.6.

Cf. A165961, A165964, A165962, A078628, A078673.

Cf. A235937, A235938, A235939, A235940, A235942, A235943.

a(n) = n^2 * A235937(n).

a(n) = n * A235939(n).

a(20)-a(21) from Alois P. Heinz, Jan 24 2014

Obsolete b-file deleted by N. J. A. Sloane, Jan 05 2019

A235942 Number of positions (cyclic permutations) of circular permutations with exactly one (unspecified) increasing or decreasing modular 3-sequence, with clockwise and counterclockwise traversals counted as distinct.

Original entry on oeis.org

0, 0, 0, 0, 50, 144, 1078, 7936, 66096, 611200, 6248682, 69926976, 850848414, 11187719984, 158122436400, 2390945284096, 38518483536706, 658706393035152, 11918123304961222, 227474585229393600, 4567806759318652080

Offset: 1

Paul J. Campbell, Jan 20 2014, with Joe Marasco and Ashish Vikram

nonn

Paul J. Campbell, Circular permutations with exactly one modular run (3-sequence), submitted to Journal of Integer Sequences

Wayne M. Dymáček and Isaac Lambert, Circular permutations avoiding runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011) Article 11.1.6.

Cf. A165961, A165964, A165962, A078628, A078673.

Cf. A235937, A235938, A235939, A235940, A235941, A235943.

a(n) = 2*n^2 * A235937(n).
a(n) = n^2 * A235938(n).
a(n) = 2*n * A235939(n).
a(n) = n * A235940(n).
a(n) = 2 * A235941(n).

a(20)-a(21) from Alois P. Heinz, Jan 24 2014

Obsolete b-file deleted by N. J. A. Sloane, Jan 05 2019

cp's OEIS Frontend

A165961 Number of circular permutations of length n without 3-sequences.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A002628 Number of permutations of length n without 3-sequences.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A174075 Number of circular permutations of length n without modular consecutive triples i,i+2,i+4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A235943 Number a(n,k) of positions (cyclic permutations) of circular permutations of [n] with exactly k (unspecified) increasing or decreasing modular runs (3-sequences), with clockwise and counterclockwise traversals counted as distinct; triangle a(n,k) read by rows, 0<=k<=n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A235937 Number of circular permutations with exactly one specified increasing or decreasing modular run (3-sequence), with clockwise and counterclockwise traversals not counted as distinct.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A235938 Number of circular permutations with exactly one specified increasing or decreasing modular run (3-sequence), with clockwise and counterclockwise traversals counted as distinct.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A235939 Number of circular permutations with exactly one (unspecified) increasing or decreasing modular 3-sequence, with clockwise and counterclockwise traversals not counted as distinct.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A235940 Number of circular permutations with exactly one (unspecified) increasing or decreasing modular 3-sequence, with clockwise and counterclockwise traversals counted as distinct.