A256208 -id:A256208 - cp's OEIS frontend

A047889 Number of permutations in S_n with longest increasing subsequence of length <= 4.

1, 1, 2, 6, 24, 119, 694, 4582, 33324, 261808, 2190688, 19318688, 178108704, 1705985883, 16891621166, 172188608886, 1801013405436, 19274897768196, 210573149141896, 2343553478425816, 26525044132374656, 304856947930144656

Offset: 0

Eric Rains (rains(AT)caltech.edu), N. J. A. Sloane

Or, number of permutations in S_n that avoid the pattern 12345, - N. J. A. Sloane, Mar 19 2015

Also, the dimension of the space of SL(4)-invariants in V^m ⊗ (V^*)^m, where V is the standard 4-dimensional representation of SL(4) and V^* its dual. - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

			G.f. = 1 + x + 2*x^2 + 6*x^3 + 24*x^4 + 119*x^5 + 694*x^6 + 4582*x^7 + ...

Gheorghe Coserea, Table of n, a(n) for n = 0..300
F. Bergeron and F. Gascon, Counting Young tableaux of bounded height, J. Integer Sequences, Vol. 3 (2000), #00.1.7.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
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.
Peter J. Forrester and Fei Wei, Higher order linear differential equations for unitary matrix integrals: applications and generalisations, arXiv:2508.20797 [math-ph], 2025.
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53 (1990), 257-285.
Permutation Pattern Avoidance Library (PermPAL), 12345
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
Index entries for sequences related to Young tableaux.

A column of A047888.
Cf. A005802, A047890, A052399.
Column k=4 of A214015.
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

A:=rsolve({a(0) = 1, a(1) = 1, (n^3 + 16*n^2 + 85*n + 150)*a(n + 2) = (20*n^3 + 182*n^2 + 510*n + 428)*a(n + 1) - (64*n^3 + 256*n^2 + 320*n +128)*a(n)}, a(n), makeproc): # Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

Flatten[{1,RecurrenceTable[{64*(-1+n)^2*n*a[-2+n]-2*(-12 + 11*n + 31*n^2 + 10*n^3)*a[-1+n] + (3+n)^2*(4+n)*a[n]==0,a[1]==1,a[2]==2},a,{n,20}]}] (* Vaclav Kotesovec, Sep 10 2014 *)

{a(n) = my(v); if( n<2, n>=0, v = vector(n+1, k, 1); for(k=2, n, v[k+1] = ((20*k^3 + 62*k^2 + 22*k - 24) * v[k] - 64*k*(k-1)^2 * v[k-1]) / ((k+3)^2 * (k+4))); v[n+1])}; /* Michael Somos, Apr 19 2015 */

a(0)=1, a(1)=1, (n^3 + 16*n^2 + 85*n + 150)*a(n+2) = (20*n^3 + 182*n^2 + 510*n + 428)*a(n+1) - (64*n^3 + 256*n^2 + 320*n + 128)*a(n). - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
a(n) = (64*(n+1)*(2*n^3 + 21*n^2 + 76*n + 89)*A002895(n) -(8*n^4 + 104*n^3 + 526*n^2 + 1098*n + 776) *A002895(n+1)) / (3*(n+2)^3*(n+3)^3*(n+4)). - Mark van Hoeij, Jun 02 2010
a(n) ~ 3 * 2^(4*n + 9) / (n^(15/2) * Pi^(3/2)). - Vaclav Kotesovec, Sep 10 2014

More terms from Naohiro Nomoto, Mar 01 2002

Edited by N. J. A. Sloane, Aug 23 2008 at the suggestion of R. J. Mathar

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

A099952 Number of Wilf classes in S_n.

Original entry on oeis.org

1, 1, 1, 3, 16, 91, 595

Offset: 1

N. J. A. Sloane, Nov 12 2004

Z. Stankova and J. West, A new class of Wilf-equivalent permutations, J. Algeb. Combin., 15 (2002), 271-290.

A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
A. M. Baxter and A. D. Jaggard, Pattern avoidance by even permutations, arXiv preprint arXiv:1106.3653, 2011
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152. See Fig. 9.

Representatives for the three Wilf classes in S_4 are A005802, A022558, A061552. - N. J. A. Sloane, Mar 15 2015

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

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

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

A256198 Number of permutations in S_n that avoid the pattern 35124.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4580, 33249, 260092, 2159381, 18815124, 170605392, 1599499163, 15427796984, 152487271455, 1539554179950, 15836801521762, 165625811815111, 1757953168747511, 18908510233855411, 205838673911323648, 2265393020812413370, 25182471016157568626

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.

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, 1, 2, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

More terms from Anthony Guttmann, Sep 29 2021

A256199 Number of permutations in S_n that avoid the pattern 53124.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4580, 33252, 260202, 2161837, 18858720, 171285237, 1609282391, 15561356705, 154246419725, 1562151687940, 16121960812335, 169178376076607, 1801800479418116, 19446010522240384, 212394673429250090, 2345064355131025130, 26148064110299271293

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, {5, 3, 1, 2, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

More terms from Anthony Guttmann, Sep 29 2021

A256201 Number of permutations in S_n that avoid the pattern 35241.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4580, 33254, 260285, 2163930, 18900534, 172016256, 1621031261, 15739870457, 156855197297, 1599233708733, 16638560125635, 176269571712376, 1898076560618372, 20742488003444465, 229747253093647567, 2576270755655436479, 29218474225923168362

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, 4, 1}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

More terms from Anthony Guttmann, Sep 29 2021

cp's OEIS Frontend

A047889 Number of permutations in S_n with longest increasing subsequence of length <= 4.

Views

Author

Keywords

Comments

Examples

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

A099952 Number of Wilf classes in S_n.

Views

Author

Keywords

References

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A256198 Number of permutations in S_n that avoid the pattern 35124.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A256199 Number of permutations in S_n that avoid the pattern 53124.