A002628 -id:A002628 - 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

A165962 Number of circular permutations of length n without modular 3-sequences.

Original entry on oeis.org

1, 5, 18, 95, 600, 4307, 35168, 321609, 3257109, 36199762, 438126986, 5736774126, 80808984725, 1218563180295, 19587031966352, 334329804347219, 6039535339644630, 115118210694558105, 2308967760171049528, 48613722701436777455, 1072008447320752890459

Offset: 3

Isaac Lambert, Oct 01 2009

nonn

Circular permutations are permutations whose indices are from the ring of integers modulo n. Modular 3-sequences are of the following form: i,i+1,i+2, where arithmetic is modulo n.

			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. - N. J. A. Sloane, Sep 15 2012

Max Alekseyev, Table of n, a(n) for n = 3..100

Cf. A002628, A165960, A165961.

First column of A216722. Cf. A216723. - N. J. A. Sloane, Sep 15 2012

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}];
Table[A165962[n],{n,3,23}] (* David Scambler, Sep 18 2012 *)

This sequence can be related to A165961 by the use of auxiliary sequences (and the auxiliary sequences can themselves be calculated by recurrence relations).

A174072 Number of permutations of length n with no consecutive triples i,i+2,i+4.

Original entry on oeis.org

1, 1, 2, 6, 24, 114, 674, 4714, 37754, 340404, 3412176, 37631268, 452745470, 5900431012, 82802497682, 1244815252434, 19958707407096, 339960096280062, 6130407887839754, 116675071758609742, 2337186717333367706, 49153251967227002616, 1082860432463176004544

Offset: 0

Isaac Lambert, Mar 06 2010

nonn

Note for n<5 there are no such subsequences, so those values are trivially n!.

			For n=5 (0,2,4,1,3) is an example of a permutation with an i,i+2,i+4 triple. If we look at 0,2,4 as a block, then we have 3! ways to permute the triple with the remaining 1 & 3. Hence a(5) = 5! - 3! = 114.

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

Cf. A002628, A174073, A174074, A174075.

First column of A216716.

b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
     `if`(x=0 or x-y<>2 or y-j<>2, b(s minus {j}, y, j), 0), j=s))
    end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..14);  # Alois P. Heinz, Apr 13 2021

b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[
     If[x == 0 || x - y != 2 || y - j != 2,
     b[s ~Complement~ {j}, y, j], 0], {j, s}]];
a[n_] := b[Range[n], 0, 0];
Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Mar 02 2022, after Alois P. Heinz *)

a(0)-a(4) and a(10)-a(11) moved from a duplicate entry based on the Dymacek et al. paper on Apr 13 2021

a(12)-a(22) from Alois P. Heinz, Apr 13 2021

A165960 Number of permutations of length n without modular 3-sequences.

Original entry on oeis.org

1, 1, 2, 3, 20, 100, 612, 4389, 35688, 325395, 3288490, 36489992, 441093864, 5770007009, 81213878830, 1223895060315, 19662509071056, 335472890422812, 6057979285535388, 115434096553014565, 2314691409652237700, 48723117262650147387, 1074208020519710570054

Offset: 0

Isaac Lambert, Oct 01 2009

nonn

Modular 3-sequences are of the following form: i,i+1,i+2, where arithmetic is modulo n.

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

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A002628, A165961, A165962.

a(n) = n * A165961(n).

a(0)-a(2) and a(15)-a(22) from Alois P. Heinz, Apr 14 2021

A174080 Number of permutations of length n with no consecutive triples i,i+d,i+2d for all d>0.

Original entry on oeis.org

1, 1, 2, 5, 21, 100, 597, 4113, 32842, 292379, 2925367, 31983248, 383514347, 4966286235, 69508102006, 1039315462467, 16627618496319, 282023014602100, 5075216962675445, 96263599713301975, 1925002914124917950

Offset: 0

Isaac Lambert, Mar 15 2010

			For n=4, there are 4!-a(4)=3 permutations with some consecutive triple i,i+d,i+2d. Note for n=4, only d=1 applies. Hence those three permutations are (0,1,2,3), (1,2,3,0), and (3,0,1,2). Since here only d=1, this is the same value of a(4) in A002628.

Cf. A002628, A174072, A174081, A174082, A174083, A295370.

b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
      `if`(x=0 or xy-j,
         b(s minus {j}, y, j), 0), j=s))
    end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..14);  # Alois P. Heinz, Apr 13 2021

b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[If[x == 0 || x < y || x-y != y-j, b[s~Complement~{j}, y, j], 0], {j, s}]];
a[n_] := b[Range[n], 0, 0];
Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Sep 27 2022, after Alois P. Heinz *)

a(0)-a(3) and a(10)-a(20) from Alois P. Heinz, Apr 13 2021

A047921 Triangle of numbers a(n,k) = number of permutations on n letters containing k 3-sequences (n >= 0, 0<=k<=max(0,n-2)).

Original entry on oeis.org

1, 1, 2, 5, 1, 21, 2, 1, 106, 11, 2, 1, 643, 62, 12, 2, 1, 4547, 406, 71, 13, 2, 1, 36696, 3046, 481, 80, 14, 2, 1, 332769, 25737, 3708, 559, 89, 15, 2, 1, 3349507, 242094, 32028, 4414, 640, 98, 16, 2, 1, 37054436, 2510733, 306723, 38893, 5164, 724, 107, 17, 2, 1

Offset: 0

N. J. A. Sloane

			Triangle begins:
       1;
       1;
       2;
       5,     1;
      21,     2,    1;
     106,    11,    2,   1;
     643,    62,   12,   2,  1;
    4547,   406,   71,  13,  2,  1;
   36696,  3046,  481,  80, 14,  2, 1;
  332769, 25737, 3708, 559, 89, 15, 2, 1;
  ...

J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.

Columns give A002628, A002629, A002630.

Row sums give A000142.

Riordan gives a recurrence.

Edited and extended by Max Alekseyev, Sep 05 2010

a(0,0) = a(1,0) = 1 prepended by Alois P. Heinz, Apr 20 2021

A132647 Number of permutations of [n] having no substring [k,k+1,k+2,k+3].

Original entry on oeis.org

1, 1, 2, 6, 23, 117, 706, 4962, 39817, 359171, 3597936, 39630372, 476066277, 6194080387, 86776390796, 1302376048620, 20847721870931, 354549730559949, 6384006047649910, 121330369923079290, 2427196999663678987, 50981866833670160201, 1121806937829102793662

Offset: 0

Ivana Jovovic (ivana121(AT)EUnet.yu), Nov 14 2007

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
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.

Cf. A000255, A002628.

seq(n)={Vec(sum(k=0, n, k!*((x^4-x)/(x^4-1) + O(x*x^n))^k))} \\ Andrew Howroyd, Aug 31 2018

G.f.: Sum_{n>=0} n!*((x^m-x)/(x^m-1))^n where m = 4.

a(n) ~ n! * (1 - 1/n^2 + 1/n^3 + 9/(2*n^4) + 7/n^5 - 55/(6*n^6) - 114/n^7 - 11419/(24*n^8) - 970/n^9 + 345199/(120*n^10) + ...). - Vaclav Kotesovec, Feb 17 2024

Terms a(16) and beyond from Andrew Howroyd, Aug 31 2018

A174084 Number of permutations of length n with no consecutive triples i,...i+r,...i+2r for all positive r, and for all equal spacings d.

Original entry on oeis.org

21, 94, 544, 3509, 26799, 223123, 2133511, 21793042, 248348572, 3008632130, 39989075942, 558800689295

Offset: 4

Isaac Lambert, Apr 20 2010

Here we count both the sequence 1,2,3 (r=1) as a progression in 1,2,3,0,4,5, (note d=1) and in 1,0,2,4,3,5 (here, d=2).

			For n=4 there are 4!-a(4)=3 with some progression. These are (0,1,2,3), (1,2,3,0), and (3,0,1,2). Here for all the progressions, r=1 and d=1, hence this term is the same as a(4) in A002628.

Cf. A002628, A174080, A174085, A174086, A174087.

Name clarified and a(10)-a(15) from Bert Dobbelaere, May 19 2025

A370390 Number of permutations of [n] whose longest block is of length 2. A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions.

Original entry on oeis.org

0, 0, 1, 2, 10, 53, 334, 2428, 20009, 184440, 1881050, 21034905, 255967940, 3367720736, 47641219569, 721160081974, 11631770791362, 199159952915293, 3607908007376418, 68946510671942892, 1386140583681969289, 29247292475233307612, 646231776371742321826

Offset: 0

Seiichi Manyama, Feb 17 2024

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..450

Column k=2 of A184182.

Cf. A000255, A002628.

my(N=30, x='x+O('x^N)); concat([0, 0], Vec(sum(k=0, N, k!*x^k*(((1-x^2)/(1-x^3))^k-((1-x)/(1-x^2))^k))))

a(n) = A002628(n) - A000255(n-1).

G.f.: Sum_{k>=0} k! * x^k * ( ((1-x^2)/(1-x^3))^k - ((1-x)/(1-x^2))^k ).

A370383 Number of permutations of [n] having no substring [k,k+1,k+2,k+3,k+4].

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 717, 5026, 40242, 362376, 3625081, 39885851, 478714416, 6224078292, 87145277160, 1307271652917, 20917481850667, 355612235468396, 6401234296266540, 121626707638142280, 2432586885636105251, 51085230669413519349, 1123891538655073251190

Offset: 0

Seiichi Manyama, Feb 17 2024

nonn

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.

Cf. A000255, A002628, A132647, A184182, A370384.

my(N=30, x='x+O('x^N)); Vec(sum(k=0, N, k!*((x-x^5)/(1-x^5))^k))

G.f.: Sum_{k>=0} k! * ( (x-x^5)/(1-x^5) )^k.

a(n) = Sum_{k=0..4} A184182(n,k). - Alois P. Heinz, Feb 17 2024

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

A165962 Number of circular permutations of length n without modular 3-sequences.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A174072 Number of permutations of length n with no consecutive triples i,i+2,i+4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A165960 Number of permutations of length n without modular 3-sequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A174080 Number of permutations of length n with no consecutive triples i,i+d,i+2d for all d>0.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A047921 Triangle of numbers a(n,k) = number of permutations on n letters containing k 3-sequences (n >= 0, 0<=k<=max(0,n-2)).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A132647 Number of permutations of [n] having no substring [k,k+1,k+2,k+3].

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A174084 Number of permutations of length n with no consecutive triples i,...i+r,...i+2r for all positive r, and for all equal spacings d.

Views