|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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
|
|
|
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
|
|
STATUS
|
approved
|
|
|
|