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

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

Author

N. J. A. Sloane, Mar 19 2015

Keywords

• nonn

Links

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

Crossrefs

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

Cf. A099952, A158434.

Programs

Mathematica

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

Formula

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

Extensions

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

More terms from Anthony Guttmann, Sep 29 2021