A099952 -id:A099952 - cp's OEIS frontend

A005802 Number of permutations in S_n with longest increasing subsequence of length <= 3 (i.e., 1234-avoiding permutations); vexillary permutations (i.e., 2143-avoiding).

1, 1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, 3763290, 24792705, 167078577, 1148208090, 8026793118, 56963722223, 409687815151, 2981863943718, 21937062144834, 162958355218089, 1221225517285209, 9225729232653663, 70209849031116183, 537935616492552297

Offset: 0

N. J. A. Sloane, Simon Plouffe

Also the dimension of SL(3)-invariants in V^n tensor (V^*)^n, where V is the standard 3-dimensional representation of SL(3) and V^* is its dual. - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
Also the number of doubly-alternating permutations of length 2n with no four-term increasing subsequence (i.e., 1234-avoiding doubly-alternating permutations). The doubly-alternating permutations (counted by sequence A007999) are those permutations w such that both w and w^(-1) have descent set {2, 4, 6, ...}. - Joel B. Lewis, May 21 2009
Any permutation without an increasing subsequence of length 4 has a decreasing subsequence of length >= n/3, where n is the length of the sequence, by the Erdős-Szekeres theorem. - Charles R Greathouse IV, Sep 26 2012
Also the number of permutations of length n simultaneously avoiding patterns 1324 and 3416725 (or 1324 and 3612745). - Alexander Burstein, Jan 31 2014

Eric S. Egge, Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics, pp. 65-82 of "A Century of Advancing Mathematics", ed. S. F. Kennedy et al., MAA Press 2015.
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(e), p. 453.

Alois P. Heinz, Table of n, a(n) for n = 0..1060
Michael Albert and Mireille Bousquet-Mélou, Permutations sortable by two stacks in parallel and quarter plane walks, arXiv:1312.4487 [math.CO], 2014-2015.
Michael Albert and Mireille Bousquet-Mélou, Permutations sortable by two stacks in parallel and quarter plane walks, European Journal of Combinatorics 43 (2015), 131-164.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
A. Burstein and J. Pantone, Two examples of unbalanced Wilf-equivalence, arXiv preprint arXiv:1402.3842 [math.CO], 2014.
CombOS - Combinatorial Object Server, Generate pattern-avoiding permutations
Andrew R. Conway and Anthony J. Guttmann, On 1324-avoiding permutations, Advances in Applied Mathematics, Volume 64, March 2015, p. 50-69.
Andrew R. Conway and Anthony J. Guttmann, Counting occurrences of patterns in permutations, arXiv:2306.12682 [math.CO], 2023. See p. 18.
Tom Denton, Algebraic and Affine Pattern Avoidance, arXiv preprint arXiv:1303.3767 [math.CO], 2013.
Eric S. Egge, Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics, MAA Focus, August/September 2015, pp. 33-34. [Annotated scanned copy]
Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r, arXiv:1504.02513 [math.CO], 2015.
Steven Finch, Pattern-Avoiding Permutations [Cached copy at the Wayback Machine]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
A. L. L. Gao, S. Kitaev, and P. B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53 (1990), 257-285.
O. Guibert and E. Pergola, Enumeration of vexillary involutions which are equal to their mirror/complement, Discrete Math., Vol. 224 (2000), pp. 281-287.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
J. Noonan and D. Zeilberger, The Enumeration of Permutations With A Prescribed Number of "Forbidden" Patterns.
J. Noonan and D. Zeilberger, The Enumeration of Permutations With A Prescribed Number of "Forbidden" Patterns, Advances in Applied Mathematics, Vol. 17, 1996, pp. 381-407.
J. Noonan and D. Zeilberger, The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns, arXiv:math/9808080 [math.CO], 1998.
Erik Ouchterlony, Pattern avoiding doubly alternating permutations
Permutation Pattern Avoidance Library (PermPAL), 0123
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
Anders Bjorner and Richard P. Stanley, A combinatorial miscellany
R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.

A column of A047888. See also A224318, A223034, A223905.
Column k=3 of A214015.
A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).

a:= n-> 2*add(binomial(2*k,k)*(binomial(n,k))^2*(3*k^2+2*k+1-n-2*k*n)/ (k+1)^2/(k+2)/(n-k+1),k=0..n);
A005802:=rsolve({a(0) = 1, a(1) = 1, (n^2 + 8*n + 16)*a(n + 2) = (10*n^2 + 42*n + 41)*a(n + 1) - (9*n^2 + 18*n + 9)*a(n)},a(n),makeproc): # Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

a[n_] := 2Sum[Binomial[2k, k]Binomial[n, k]^2(3k^2+2k+1-n-2k*n)/((k+1)^2(k+2)(n-k+1)), {k, 0, n}]
(* Second program:*)
a[0] = a[1] = 1; a[n_] := a[n] = ((10*n^2+2*n-3)*a[n-1] + (-9*n^2+18*n-9)* a[n-2])/(n+2)^2; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 20 2017 *)
Table[HypergeometricPFQ[{1/2, -1 - n, -n}, {2, 2}, 4] / (n+1), {n, 0, 25}] (* Vaclav Kotesovec, Jun 07 2021 *)

a(n)=2*sum(k=0,n,binomial(2*k,k)*binomial(n,k)^2*(3*k^2+2*k+1-n-2*k*n)/(k+1)^2/(k+2)/(n-k+1)) \\ Charles R Greathouse IV, Sep 26 2012

a(n) = 2 * Sum_{k=0..n} binomial(2*k, k) * (binomial(n, k))^2 * (3*k^2 + 2*k+1 - n - 2*k*n)/((k+1)^2 * (k+2) * (n-k+1)).
(4*n^2 - 2*n + 1)*(n + 2)^2*(n + 1)^2*a(n) = (44*n^3 - 14*n^2 - 11*n + 8)*n*(n + 1)^2*a(n - 1) - (76*n^4 + 42*n^3 - 49*n^2 - 24*n + 24)*(n - 1)^2*a(n - 2) + 9*(4*n^2 + 6*n + 3)*(n - 1)^2*(n - 2)^2*a(n - 3). - Vladeta Jovovic, Jul 16 2004
a(0) = 1, a(1) = 1, (n^2 + 8*n + 16)*a(n + 2) = (10*n^2 + 42*n + 41) a(n + 1) - (9*n^2 + 18*n + 9) a(n). - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
a(n) = ((18*n+45)*A002893(n) - (7+2*n)*A002893(n+1)) / (6*(n+2)^2). - Mark van Hoeij, Jul 02 2010
G.f.: (1+5*x-(1-9*x)^(3/4)*(1-x)^(1/4)*hypergeom([-1/4, 3/4],[1],64*x/((x-1)*(1-9*x)^3)))/(6*x^2). - Mark van Hoeij, Oct 25 2011
a(n) ~ 3^(2*n+9/2)/(16*Pi*n^4). - Vaclav Kotesovec, Jul 29 2013
a(n) = Sum_{k=0..n} binomial(2k,k)*binomial(n+1,k+1)*binomial(n+2,k+1)/((n+1)^2*(n+2)). [Conway and Guttmann, Adv. Appl. Math. 64 (2015) 50]
For n > 0, (n+2)^2*a(n) - n^2*a(n-1) = 4*A086618(n). - Zhi-Wei Sun, Nov 16 2017
a(n) = hypergeom([1/2, -1 - n, -n], [2, 2], 4) / (n+1). - Vaclav Kotesovec, Jun 07 2021

Additional comments from Emeric Deutsch, Dec 06 2000
More terms from Naohiro Nomoto, Jun 18 2001
Edited by Dean Hickerson, Dec 10 2002
More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

A116485 Number of permutations in S_n that avoid the pattern 12453 (or equivalently, 31245).

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4581, 33286, 260927, 2174398, 19053058, 174094868, 1648198050, 16085475576, 161174636600, 1652590573612, 17292601075489, 184246699159418, 1995064785620557, 21919480341617102, 244015986016996763, 2749174129340156922, 31313478171012371344

Offset: 0

Zvezdelina Stankova (stankova(AT)mills.edu), Mar 19 2006

nonn

a(n) is also the number of permutations in S_n that avoid the pattern 21453 or any of its symmetries. The Wilf class consists of 16 permutations. - David Bevan, Jun 17 2021

Yonah Biers-Ariel, Table of n, a(n) for n = 0..37
Yonah Biers-Ariel, Julia program to compute terms
Miklos Bona, The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns, arXiv:math/0403502 [math.CO], 2004.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208. - N. J. A. Sloane, Mar 19 2015

Cf. A099952, A158423.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {1, 2, 4, 5, 3}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

Conjecture: a(n) + A158423(n) = n!. - Benedict W. J. Irwin, Mar 15 2016
The conjecture is true: All that is needed is to show that 23145 is Wilf-equivalent to 31245, but that’s obvious since they are inverses. - Doron Zeilberger and Yonah Biers-Ariel, Feb 26 2019
The exponential growth rate is 9+4*sqrt(2). See [Bona 2004]. - David Bevan, Jun 17 2021

More terms from the Zvezdelina Stankova-Frenkel and Julian West paper. - N. J. A. Sloane, Mar 19 2015
More terms from Doron Zeilberger and Yonah Biers-Ariel, Feb 26 2019
More terms from Yonah Biers-Ariel, Mar 04 2019

A022558 Number of permutations of length n avoiding the pattern 1342.

Original entry on oeis.org

1, 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, 3475090, 22214707, 144640291, 956560748, 6411521056, 43478151737, 297864793993, 2059159989914, 14350039389022, 100726680316559, 711630547589023, 5057282786190872, 36132861123763276, 259423620328055093

Offset: 0

Miklos Bona

Differs from A117156 which counts permutations avoiding the *consecutive* pattern 1342. - Ray Chandler, Dec 06 2011
Also, number of permutation of length n avoiding the pattern 3142 (see Stankova (1994) below). - Alexander Burstein, Aug 09 2013
Conjecture: a(n) is the number of permutations of length n simultaneously avoiding patterns 2143 and 415263. - Alexander Burstein, Mar 21 2019

			a(4) = 23 because obviously all permutations of length 4 with the exception of 1342 avoid 1342.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 768, Th. 12.1.14.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.48.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
Miklos Bona, Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps, arXiv:math/9702223 [math.CO], 1997.
Miklos Bona, Exact enumeration of 1342-avoiding permutations; A close link with labeled trees and planar maps, J. Combinatorial Theory, A80 (1997), 257-272.
Alexander Burstein and Jay Pantone, Two examples of unbalanced Wilf-equivalence, J. Combin. 6 (2015), no. 1-2, 55-67.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
A. R. Conway and A. J. Guttmann, On 1324-avoiding permutations, Adv. Appl. Math. 64 (2015), 50-69.
A. L. L. Gao, S. Kitaev, and P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint arXiv:1410.2657 [math.CO], 2014.
Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
W. Mlotkowski, K. A. Penson, A Fuss-type family of positive definite sequences, arXiv:1507.07312 (2015), eq. (36).
Z. E. Stankova, Forbidden subsequences, Discrete Math., 132 (1994), no. 1-3, 291-316.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001. See Fig. 11.

Essentially the same as A004040.
Cf. A117158.
A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).

a := proc (n) options operator, arrow: (1/2)*(-1)^(n-1)*(7*n^2-3*n-2)+3*(sum((-1)^(n-i)*2^(i+1)*factorial(2*i-4)*binomial(n-i+2, 2)/(factorial(i)*factorial(i-2)), i = 2 .. n)) end proc: seq(a(n), n = 0 .. 30); # Emeric Deutsch, Oct 15 2014

Table[SeriesCoefficient[32*x/(1+20*x-8*x^2-(1-8*x)^(3/2)),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 07 2012 *)
Table[1/2*(-1)^(n-1) * (-2-3*n+7*n^2) + 1/4*(-1)^n * (1+n) * (-2-13*n+(n+2) * Hypergeometric2F1[-3/2,-n,-2-n,-8]),{n,0,20}] (* Vaclav Kotesovec, Aug 24 2014 *)

x='x+O('x^66); Vec( 32*x/(1+20*x-8*x^2-(1-8*x)^(3/2)) ) \\ Joerg Arndt, May 04 2013

a(n) = (7*n^2-3*n-2)/2 * (-1)^(n-1) + 3*Sum_{i=2..n} 2^(i+1) * (2*i-4)!/(i!*(i-2)!) * binomial(n-i+2, 2) * (-1)^(n-i).
G.f.: 32*x/(1 + 20*x - 8*x^2 - (1 - 8*x)^(3/2)). - Emeric Deutsch, Mar 13 2004
Recurrence: n*a(n) = (7*n-22)*a(n-1) + 4*(2*n-1)*a(n-2). - Vaclav Kotesovec, Oct 07 2012
a(n) ~ 2^(3*n+6)/(243*sqrt(Pi)*n^(5/2)). - Vaclav Kotesovec, Oct 07 2012

Minor edits by Vaclav Kotesovec, Aug 24 2014

A256195 Number of permutations in S_n that avoid the pattern 25314.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4578, 33184, 258757, 2136978, 18478134, 165857600, 1535336290, 14584260700, 141603589300, 1400942032152, 14087464765300, 143689133196008, 1484090443264936, 15499968503875136, 163501005435759505, 1740170514634463426, 18671118911254798454

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..26
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {2, 5, 3, 1, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

a(14)-a(16) from Bert Dobbelaere, Mar 18 2021

More terms from Anthony Guttmann, Sep 29 2021

A256208 Number of permutations in S_n that avoid the pattern 52341.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4582, 33325, 261863, 2192390, 19358590, 178904675, 1720317763, 17132629082, 176055309619, 1861037944163, 20185165186517, 224150069984572, 2543698932578158, 29451619807433107, 347417296695040510, 4170088041714300134, 50874753262007210667

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..23
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {5, 2, 3, 4, 1}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

More terms from Anthony Guttmann, Sep 29 2021

A061552 Number of 1324-avoiding permutations of length n.

Original entry on oeis.org

1, 1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, 3824112, 25431452, 173453058, 1209639642, 8604450011, 62300851632, 458374397312, 3421888118907, 25887131596018, 198244731603623, 1535346218316422, 12015325816028313, 94944352095728825, 757046484552152932, 6087537591051072864

Offset: 0

Darko Marinov (marinov(AT)lcs.mit.edu), May 17 2001

nonn

			a(4)=23 because all 24 permutations of length 4, except 1324 itself, avoid the pattern 1324.

Miklós Bóna, Combinatorics of Permutations. Discrete Mathematics and its Applications (Boca Raton), 2nd edn. CRC Press, Boca Raton (2012).

David Bevan, Table of n, a(n) for n = 0..50 (from the Conway/Guttmann reference; terms 0..31 by Joerg Arndt, taken from the Johansson/Nakamura reference; terms 37..50 by Bjarki Ágúst Guðmundsson, taken from the Conway/Guttmann/Zinn-Justin reference).
M. H. Albert, M. Elder, A. Rechnitzer, P. Westcott, and M. Zabrocki, On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia, arXiv:math/0502504 [math.CO], 2005.
R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern., Electron. J. Combin. 6, N1 (1999).
David Bevan, Permutations avoiding 1324 and patterns in Łukasiewicz paths, arXiv:1406.2890 [math.CO], 2014-2015.
David Bevan, Robert Brignall, Andrew Elvey Price and Jay Pantone, A structural characterisation of Av(1324) and new bounds on its growth rate, European J. Combin. 88 (2020).
Miklós Bóna, A new upper bound for 1324-avoiding permutations, arXiv:1207.2379 [math.CO], 2012.
Miklós Bóna, A new upper bound for 1324-avoiding permutations, Combin. Probab. Comput. 23(5), 717-724 (2014).
Miklós Bóna, A new record for 1324-avoiding permutations, arXiv:1404.4033 [math.CO], 2014.
Miklós Bóna, A new record for 1324-avoiding permutations, European Journal of Mathematics (2015) 1:198-206, DOI 10.1007/s40879-014-0020-6.
A. Claesson, V. Jelínek, and E. Steingrímsson, Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns. J. Combin. Theory Ser. A 119(8), 1680-1691 (2012).
Andrew R. Conway and Anthony J. Guttmann, On the growth rate of 1324-avoiding permutations, arXiv:1405.6802 [math.CO], (2014).
Andrew R. Conway, Anthony J. Guttmann and Paul Zinn-Justin, 1324-avoiding permutations revisited, arXiv preprint arXiv:1709.01248 [math.CO], 2017.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
A. L. L. Gao, S. Kitaev, and P. B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
Ruth Hoffmann, Özgür Akgün, and Christopher Jefferson, Composable Constraint Models for Permutation Enumeration, arXiv:2311.17581 [cs.DM], 2023.
Fredrik Johansson and Brian Nakamura, Using functional equations to enumerate 1324-avoiding permutations, arXiv:1309.7117 [math.CO], (2013).
A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107(1), 153-160 (2004).
B. K. Nakamura, Computational methods in permutation patterns, PhD Dissertation, Rutgers University, May 2013.
Brian Nakamura and Doron Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes, arXiv preprint arXiv:1209.2353 [math.CO], 2012.
Anthony Zaleski and Doron Zeilberger, On the Intriguing Problem of Counting (n+1,n+2)-Core Partitions into Odd Parts, arXiv:1712.10072 [math.CO], 2017.

A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).

count1324 := proc(n::nonnegint) if (n<4) then return n!; fi; if (n=4) then return 23; fi; return nodes([5,5,5,5], n-5) + nodes([5,3,5,5], n-5) + nodes([5,4,4,5], n-5) + nodes([5,5,4,5], n-5) + nodes([4,3,4], n-5) + nodes([5,3,4,5], n-5); end:
nodes := proc(p, h) option remember; local i, j, s, l; if (h=0) then return convert(p, `+`); fi; s := 0; for j to nops(p) do l := p[j]+1; for i from 2 to j do l := l, `min`(j+1, p[i]); od; for i from j+1 to p[j] do l := l, p[i-1]+1; od; s := s+nodes([l], h-1); od; return s; end:

a[n_] := n!/;n<4; a[4]=23; a[n_] := Total[nodes[#,n-5]&/@{{4,3,4},{5,3,4,5},{5,3,5,5},{5,4,4,5},{5,5,4,5},{5,5,5,5}}]; nodes[p_,0]:=Total[p]; nodes[p_,h_] := nodes[p,h] = Sum[nodes[Join[{p[[j]]+1}, Min[j+1,#]&/@p[[2;;j]], p[[j;;p[[j]]-1]]+1],h-1], {j,Length[p]}]; Array[a,12] (* David Bevan, May 25 2012 *)

More terms from Vincent Vatter, Feb 26 2005

a(23)-a(25) added from the Albert et al. paper by N. J. A. Sloane, Mar 29 2013

A000903 Number of inequivalent ways of placing n nonattacking rooks on n X n board up to rotations and reflections of the board.

Original entry on oeis.org

1, 1, 2, 7, 23, 115, 694, 5282, 46066, 456454, 4999004, 59916028, 778525516, 10897964660, 163461964024, 2615361578344, 44460982752488, 800296985768776, 15205638776753680, 304112757426239984, 6386367801916347184

Offset: 1

N. J. A. Sloane

			For n=4 the 7 solutions may be taken to be 1234,1243,1324,1423,1432,2143,2413.

L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.
R. C. Read, personal communication.
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).
Z. Stankova and J. West, A new class of Wilf-equivalent permutations, J. Algeb. Combin., 15 (2002), 271-290.

N. J. A. Sloane, Table of n, a(n) for n = 1..100
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181. [Annotated scan of pages 180 and 181 only]
E. Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 222.
E. Lucas, Théorie des nombres (annotated scans of a few selected pages)
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).
R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976). (Annotated scanned copy)
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001. See Fig. 9.
Eric Weisstein's World of Mathematics, Rook Number.
Eric Weisstein's World of Mathematics, Rooks Problem.

Cf. A000142, A037223, A037224, A000085, A005635, A099952, A263685.

Maple programs for A000142, A037223, A122670, A001813, A000085, A000898, A000407, A000902, A000900, A000901, A000899, A000903
P:=n->n!; # Gives A000142
G:=proc(n) local k; k:=floor(n/2); k!*2^k; end; # Gives A037223, A000165
R:=proc(n) local m; if n mod 4 = 2 or n mod 4 = 3 then RETURN(0); fi; m:=floor(n/4); (2*m)!/m!; end; # Gives A122670, A001813
unprotect(D); D:=proc(n) option remember; if n <= 1 then 1 else D(n-1)+(n-1)*D(n-2); fi; end; # Gives A000085
B:=proc(n) option remember; if n <= 1 then RETURN(1); fi; if n mod 2 = 1 then RETURN(B(n-1)); fi; 2*B(n-2) + (n-2)*B(n-4); end; # Gives A000898 (doubled up)
rho:=n->R(n)/2; # Gives A000407, aerated
beta:=n->B(n)/2; # Gives A000902, doubled up
delta:=n->(D(n)-B(n))/2; # Gives A000900
unprotect(gamma); gamma:=n-> if n <= 1 then RETURN(0) else (G(n)-B(n)-R(n))/4; fi; # Gives A000901, doubled up
alpha:=n->P(n)/8-G(n)/8+B(n)/4-D(n)/4; # Gives A000899
unprotect(sigma); sigma:=n-> if n <= 1 then RETURN(1); else P(n)/8+G(n)/8+R(n)/4+D(n)/4; fi; #Gives A000903

c[n_] := Floor[n/2]! 2^Floor[n/2];
r[n_] := If[Mod[n, 4] > 1, 0, m = Floor[n/4]; If[m == 0, 1, (2 m)!/m!]];
d[0] = d[1] = 1; d[n_] := d[n] = (n - 1)d[n - 2] + d[n - 1];
a[1] = 1; a[n_] := (n! + c[n] + 2 r[n] + 2 d[n])/8;
Array[a, 21] (* Jean-François Alcover, Apr 06 2011, after Matthias Engelhardt, further improved by Robert G. Wilson v *)

If n>1 then a(n) = 1/8 * (F(n) + C(n) + 2 * R(n) + 2 * D(n)), where F(n) = A000142(n) [all solutions, i.e., factorials], C(n) = A037223(n) [central symmetric solutions], R(n) = A037224(n) [rotationally symmetric solutions] and D(n) = A000085(n) [symmetric solutions by reflection at a diagonal]. - Matthias Engelhardt, Apr 05 2000

For asymptotics see the Robinson paper.

More terms from David W. Wilson, Jul 13 2003

A256200 Number of permutations in S_n that avoid the pattern 42351.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4580, 33252, 260204, 2161930, 18861307, 171341565, 1610345257, 15579644765, 154541844196, 1566713947713, 16190122718865, 170171678529883, 1816001425551270, 19646035298044543, 215179180467834605, 2383465957654163227, 26673704385975326866

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..27
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952, A158434.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {4, 2, 3, 5, 1}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

a(n) = n! - A158434(n). - Andrew Howroyd, May 18 2020

a(14)-a(15) added by Andrew Howroyd, May 18 2020

More terms from Anthony Guttmann, Sep 29 2021

A256196 Number of permutations in S_n that avoid the pattern 31524.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4579, 33216, 259401, 2147525, 18632512, 167969934, 1563027614, 14937175825, 146016423713, 1455402205257, 14753501614541, 151783381341695, 1582029822426003, 16681492660789425, 177726496203056670, 1911230701872865231, 20726637978574528119

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..25
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {3, 1, 5, 2, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

a(14)-a(16) from Bert Dobbelaere, Mar 18 2021

More terms from Anthony Guttmann, Sep 29 2021

A256197 Number of permutations in S_n that avoid the pattern 35214.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4579, 33218, 259483, 2149558, 18672277, 168648090, 1573625606, 15093309024, 148223240022, 1485673163882, 15159644212775, 157142812302992, 1651865171372967, 17582693993265148, 189269329080075275, 2058215511081891400, 22589841589522026553

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..26
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {3, 5, 2, 1, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

More terms from Anthony Guttmann, Sep 29 2021

cp's OEIS Frontend

A005802 Number of permutations in S_n with longest increasing subsequence of length <= 3 (i.e., 1234-avoiding permutations); vexillary permutations (i.e., 2143-avoiding).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A116485 Number of permutations in S_n that avoid the pattern 12453 (or equivalently, 31245).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A022558 Number of permutations of length n avoiding the pattern 1342.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A256195 Number of permutations in S_n that avoid the pattern 25314.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A256208 Number of permutations in S_n that avoid the pattern 52341.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A061552 Number of 1324-avoiding permutations of length n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A000903 Number of inequivalent ways of placing n nonattacking rooks on n X n board up to rotations and reflections of the board.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs