A095816 -id:A095816 - cp's OEIS frontend

A078628 Number of ways of arranging the numbers 1..n in a circle so that there is no consecutive triple i, i+1, i+2 or i, i-1, i-2 (mod n).

1, 1, 0, 4, 12, 76, 494, 3662, 30574, 284398, 2918924, 32791604, 400400062, 5281683678, 74866857910, 1135063409918, 18330526475060, 314169905117860, 5695984717957246, 108921059813769710, 2190998123920252622, 46250325111346491694

Offset: 1

N. J. A. Sloane, Dec 12 2002

nonn

This sequence can be related to A165964 by the use of auxiliary sequences (and the auxiliary sequences can themselves be calculated by recurrence relations). So if we desire we can determine any value of this sequence. [From Isaac Lambert, Oct 07 2009]

			a(4) = 4: 4 2 1 3, 4 3 1 2, 4 1 3 2, 4 2 3 1.
a(5) = 12: 5 3 1 2 4, 5 2 3 1 4, 5 4 2 1 3, 5 2 4 1 3, 5 1 4 2 3, 5 2 1 4 3, 5 1 3 4 2, 5 3 1 4 2, 5 4 1 3 2, 5 3 4 1 2, 5 2 4 3 1, 5 3 2 4 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 14 2012

Isaac Lambert, Table of n, a(n) for n = 1..50
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.
Sean A. Irvine, Java program (github)
N. J. A. Sloane, FORTRAN program
Index entries for sequences related to shoe lacings

Cf. A078673. See A002816, A078603 for analogous sequence with restrictions only on pairs.

Cf. A095816, A165963, A165964.

a(11)-a(13) from John W. Layman, Nov 15 2004

a(14) from Isaac Lambert, Oct 07 2009

A165964 Number of circular permutations of length n without increasing or decreasing 3-sequences.

Original entry on oeis.org

1, 1, 0, 4, 16, 86, 542, 3932, 32330, 297438, 3028320, 33814454, 410954878, 5400878692, 76329470882, 1154445436334, 18606430004984, 318369275913710, 5764046146341198, 110091446931897180, 2212282487296335866, 46658484076867264702, 1030533208360458081232

Offset: 1

Isaac Lambert, Oct 07 2009

nonn

Circular permutations are permutations whose indices are from the ring of integers modulo n. Increasing 3-sequences are of the form i,i+1,i+2, while decreasing 3-sequences are of the form i,i-1,i-2.

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

Alois P. Heinz, Table of n, a(n) for n = 1..450
W. M. Dymacek, I. Lambert, Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2 , J. Int. Seq. 14 (2011) # 11.1.6, Table 1.

Cf. A095816, A165963, A078628.

a(n) = A095816(n-1) - 2 * Sum_{i=1..[(n+1)/3]} (A095816(n-3*i) - A095816(n-1-3*i)). [Corrected by Sean A. Irvine, Jul 07 2025]

Edited and more terms added by Max Alekseyev, Jun 14 2011

A165963 Number of permutations of length n without increasing or decreasing modular 3-sequences.

Original entry on oeis.org

0, 16, 80, 516, 3794, 31456, 290970, 2974380, 33311520, 405773448, 5342413414, 75612301688

Offset: 3

Isaac Lambert, Oct 07 2009

nonn

Increasing modular 3-sequences are of the following form: i,i+1,i+2, where arithmetic is modulo n, while correspondingly decreasing modular 3-sequences are of the form i,i-1,i-2, where arithmetic is modulo n.

			For n=4 there are a(4)=16 solutions, thus there are 4!-a(4)=8 permutations of length 4 with increasing or decreasing modular 3-sequences. These are the permutations (0,1,2,3), (0,3,2,1), (1,2,3,0), (1,0,3,2), (2,3,0,1), (2,1,0,3), (3,0,1,2), and (3,2,1,0).

W. M. Dymacek, I. Lambert, Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2 , J. Int. Seq. 14 (2011) # 11.1.6, Table 1.

Cf. A095816, A165964, A078628.

Let b(n) be the sequence A165964. Then this sequence a(n)=n(b(n)).

A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i

Original entry on oeis.org

1, 0, 2, 2, 8, 14, 54, 128, 498, 1426, 5736, 18814, 78886, 287296, 1258018, 4986402, 22789000, 96966318, 461790998, 2088374592, 10343408786, 49343711666, 253644381032, 1268995609502, 6756470362374, 35285321738624, 194220286045506, 1054759508543554

Offset: 0

Alois P. Heinz, May 19 2023

nonn

Number of permutations p of [n] such that each element in p has at least one neighbor whose value is smaller or larger by one.

Number of permutations of [n] having n occurrences of the 1-box pattern.

			a(0) = 1: (), the empty permutation.
a(1) = 0.
a(2) = 2: 12, 21.
a(3) = 2: 123, 321.
a(4) = 8: 1234, 1243, 2134, 2143, 3412, 3421, 4312, 4321.
a(5) = 14: 12345, 12354, 12543, 21345, 21543, 32145, 32154, 34512, 34521, 45123, 45321, 54123, 54312, 54321.
a(6) = 54: 123456, 123465, 123654, 124356, 124365, 125634, 125643, 126534, 126543, 213456, 213465, 214356, 214365, 215634, 215643, 216534, 216543, 321456, 321654, 341256, 341265, 342156, 342165, 345612, 345621, 346512, 346521, 431256, 431265, 432156, 432165, 435612, 435621, 436512, 436521, 456123, 456321, 561234, 561243, 562134, 562143, 563412, 563421, 564312, 564321, 651234, 651243, 652134, 652143, 653412, 653421, 654123, 654312, 654321.

Alois P. Heinz, Table of n, a(n) for n = 0..803
FindStat, St000064: The number of one-box pattern of a permutation.
S. Kitaev, J. Remmel, The 1-box pattern on pattern avoiding permutations, arXiv:1305.6970 [math.CO], 2013.

Main diagonal of A346462.

Cf. A002464, A003274, A011655, A095816, A127697, A179957, A229730, A271212, A211694, A333833, A363236.

a:= proc(n) option remember; `if`(n<4, [1, 0, 2$2][n+1],
      3/2*a(n-1)+(n-3/2)*a(n-2)-(n-5/2)*a(n-3)+(n-4)*a(n-4))
    end:
seq(a(n), n=0..30);

a(n) = A346462(n,n).
a(n)/2 mod 2 = A011655(n-1) for n>=1.
a(n) ~ sqrt(Pi) * n^((n+1)/2) / (2 * exp(n/2 - sqrt(n)/2 + 7/16)) * (1 - 119/(192*sqrt(n))). - Vaclav Kotesovec, May 26 2023

A095818 Number of permutations of 1..n with no five elements in correct or reverse order.

Original entry on oeis.org

1, 1, 2, 6, 24, 118, 714, 5012, 40164, 361872, 3621366, 39854930, 478427452, 6221137644, 87112280208, 1306869108686, 20912175669082, 355537064658852, 6400095163337508, 121608318630457872, 2432271817858395382, 51079520016325649394, 1123782363517325646716

Offset: 0

Jonas Wallgren, Jun 08 2004

nonn

For no k do either of the subsequences k(k+1)(k+2)(k+3)(k+4) or (k+4)(k+3)(k+2)(k+1)k occur in any permutation.

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. A002464, A095816, A095817.

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

G.f.: Sum_{n>=0} n!*((2*x^m-x^(m+1)-x)/(x^m-1))^n where m = 5. - Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

More terms from Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

a(0)=1 prepended and terms a(20) and beyond from Andrew Howroyd, Aug 31 2018

A174076 Number of permutations of length n with no consecutive triples i,i+2,i+4 or i,i-2,i-4.

Original entry on oeis.org

1, 1, 2, 6, 24, 108, 632, 4408, 35336, 319056, 3205824, 35451984, 427683560, 5588310904, 78615281768, 1184587864512, 19033796498496, 324852522308160, 5868833343451592, 111889157407344424

Offset: 0

Isaac Lambert, Mar 10 2010

Note for n<5 there are no such subsequences, so those values are trivially n!. Also note it is possible for a permutation to have both i,i+2,i+4 and i,i-2,i-4 triples, as in an example from n=7: (2,4,6,5,3,1,0). This permutation is not counted by a(7).

			For n=5 there are 5!-a(5)=12 permutations with i,i+2,i+4 or i,i-2,i-4 triples. An examples of one is (4,2,0,1,3).

Cf. A095816, A174077, A174078, A174079.

a(0)-a(4) and a(10)-a(19) from Alois P. Heinz, Apr 14 2021

A174081 Number of permutations of length n with no consecutive triples i,i+d,i+2d (mod n) for all d.

Original entry on oeis.org

16, 40, 300, 1764, 17056, 118908, 1466840, 14079340, 184672896, 2206738248, 33901722288, 458478528000

Offset: 4

Isaac Lambert, Mar 15 2010

nonn

			For n=4, there are 4!-a(4)=8 permutations with some consecutive triple i,i+d,i+2d (mod 4). Here only d=1 and d=3 works, and the permutations are (0,1,2,3), (1,2,3,0), (2,3,0,1), (3,0,1,2), (0,3,2,1), (3,2,1,0), (2,1,0,3), and (1,0,3,2)

Cf. A095816, A174073, A174080, A174082, A174083.

a(10)-a(15) from Bert Dobbelaere, May 18 2025

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

Original entry on oeis.org

1, 1, 2, 4, 18, 72, 396, 2328, 17050, 131764, 1199368, 11379524, 123012492, 1386127700, 17450444866, 227152227940

Offset: 0

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

Number of permutations of 1..n with no 2-dimensional arithmetic progression of length 3: that is, no three points (i,p(i)), (j,p(j)) and (k,p(k)) such that j-i = k-j and p(j)-p(i) = p(k)-p(j). - David Bevan, Jun 16 2021

			a(3) = 4; 123 and 321 each contain a 3-term arithmetic progression.
Since the only possibilities for progressions for n=4 are d=1 and r=1 and -1, we get the same term as A095816(4).

Cf. A095816, A174084, A174086, A174087.
Cf. A179040 (number of permutations of 1..n with no three elements collinear).
Cf. A003407 for another interpretation of avoiding 3-term APs.

a(n) >= A003407(n) with equality only for n in {0, 1, 2, 3}.

a(0)-a(3) and a(10)-a(13) from David Bevan, Jun 16 2021

a(14)-a(15) from Bert Dobbelaere, May 18 2025

A095817 Number of permutations of 1..n with no four elements in correct or reverse order.

Original entry on oeis.org

1, 1, 2, 6, 22, 114, 692, 4884, 39318, 355490, 3567292, 39345804, 473148014, 6161310442, 86376341412, 1297099489668, 20772929663254, 353415786538434, 6365693021157116, 121016486728717740, 2421505946364174606, 50873034832373299370, 1119617627206173146308

Offset: 0

Jonas Wallgren, Jun 08 2004

nonn

For no k do either of the subsequences k(k+1)(k+2)(k+3) or (k+3)(k+2)(k+1)k occur in any permutation.

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. A002464, A095816, A095818.

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

G.f.: Sum_{n>=0} n!*((2*x^m-x^(m+1)-x)/(x^m-1))^n where m = 4. - Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

More terms from Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

a(0)=1 prepended and terms a(20) and beyond from Andrew Howroyd, Aug 31 2018

A340106 Triangle read by rows: T(n,k) is the number of permutations of k elements from [1..n] with longest consecutive chain size less than 3.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 4, 1, 4, 12, 20, 18, 1, 5, 20, 54, 100, 92, 1, 6, 30, 112, 318, 600, 570, 1, 7, 42, 200, 768, 2208, 4244, 4082, 1, 8, 56, 324, 1570, 6080, 17682, 34300, 33292, 1, 9, 72, 490, 2868, 13980, 54552, 159702, 311808, 304490, 1, 10, 90, 704, 4830, 28392, 139130, 545528, 1604616, 3147164, 3086890

Offset: 0

Xiangyu Chen, Dec 28 2020

In a convex n-gon, the number of paths using k non-repeated vertices and fewer than 3 vertices (2 sides) in a row, except side (1,n) is unrestricted.

			n\k   0     1      2      3      4     5     6     7     8
0     1
1     1     1
2     1     2      2
3     1     3      6      4
4     1     4     12     20     18
5     1     5     20     54    100    92
6     1     6     30    112    318   600    570
7     1     7     42    200    768  2208   4244  4082
8     1     8     56    324   1570  6080  17682 34300 33292

Right diagonal is A095816.
Cf. A338526, A338838, A338849.
Cf. A340107, A340108.

T(n,k) = A340107(n,k) + 2*O(n-1,k-1) + O(n-2,k-2), where O(n,k) = 2*(k-1)*T(n-1,k-1)/(n-1) - 2*O(n-1,k-1) + 3*O(n-2,k-2) + 2*O(n-3,k-3) + O(n-4,k-4), O(n,k)=0 for k<=1.

cp's OEIS Frontend

A078628 Number of ways of arranging the numbers 1..n in a circle so that there is no consecutive triple i, i+1, i+2 or i, i-1, i-2 (mod n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A165964 Number of circular permutations of length n without increasing or decreasing 3-sequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A165963 Number of permutations of length n without increasing or decreasing modular 3-sequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A095818 Number of permutations of 1..n with no five elements in correct or reverse order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A174076 Number of permutations of length n with no consecutive triples i,i+2,i+4 or i,i-2,i-4.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A174081 Number of permutations of length n with no consecutive triples i,i+d,i+2d (mod n) for all d.

Views

Author

Keywords

Examples

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A095817 Number of permutations of 1..n with no four elements in correct or reverse order.

Views

Author

Keywords