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

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

Author

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

Keywords

• nonn

Comments

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

Links

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

Crossrefs

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.

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

Formula

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

Extensions

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