cp's OEIS Frontend

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

%I A116485 #69 Jun 18 2021 10:54:33
%S A116485 1,1,2,6,24,119,694,4581,33286,260927,2174398,19053058,174094868,
%T A116485 1648198050,16085475576,161174636600,1652590573612,17292601075489,
%U A116485 184246699159418,1995064785620557,21919480341617102,244015986016996763,2749174129340156922,31313478171012371344
%N A116485 Number of permutations in S_n that avoid the pattern 12453 (or equivalently, 31245).
%C A116485 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
%H A116485 Yonah Biers-Ariel, <a href="/A116485/b116485.txt">Table of n, a(n) for n = 0..37</a>
%H A116485 Yonah Biers-Ariel, <a href="/A116485/a116485_1.txt">Julia program to compute terms</a>
%H A116485 Miklos Bona, <a href="http://arxiv.org/abs/math/0403502">The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns</a>, arXiv:math/0403502 [math.CO], 2004.
%H A116485 Zvezdelina Stankova-Frenkel and Julian West, <a href="http://arxiv.org/abs/math/0103152">A new class of Wilf-equivalent permutations</a>, arXiv:math/0103152 [math.CO], 2001.
%F A116485 Conjecture: a(n) + A158423(n) = n!. - _Benedict W. J. Irwin_, Mar 15 2016
%F A116485 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
%F A116485 The exponential growth rate is 9+4*sqrt(2). See [Bona 2004]. - _David Bevan_, Jun 17 2021
%t A116485 avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
%t A116485     lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
%t A116485     psn = Permutations[Range[n]]},
%t A116485    For[i = 1, i <= Length[lpat], i++,
%t A116485     p = lpat[[i]];
%t A116485     AppendTo[lseq, Select[psn, MemberQ[#, {___, p[[p1]], ___, p[[p2]], ___, p[[p3]], ___, p[[p4]], ___, p[[p5]], ___}, {0}] &]];
%t A116485     ]; n! - Length[Union[Flatten[lseq, 1]]]];
%t A116485 Table[avoid[n, {1, 2, 4, 5, 3}], {n, 0, 8}]  (* _Robert Price_, Mar 27 2020 *)
%Y A116485 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
%Y A116485 Cf. A099952, A158423.
%K A116485 nonn
%O A116485 0,3
%A A116485 Zvezdelina Stankova (stankova(AT)mills.edu), Mar 19 2006
%E A116485 More terms from the Zvezdelina Stankova-Frenkel and Julian West paper. - _N. J. A. Sloane_, Mar 19 2015
%E A116485 More terms from _Doron Zeilberger_ and _Yonah Biers-Ariel_, Feb 26 2019
%E A116485 More terms from _Yonah Biers-Ariel_, Mar 04 2019