login
A116485
Number of permutations in S_n that avoid the pattern 12453 (or equivalently, 31245).
26
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,3
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
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.
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
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 *)
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
Sequence in context: A256203 A256204 A256205 * A256206 A052397 A047889
KEYWORD
nonn
AUTHOR
Zvezdelina Stankova (stankova(AT)mills.edu), Mar 19 2006
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
STATUS
approved