|
%I #98 Dec 05 2023 17:22:09
%S 1,1,2,6,23,103,513,2762,15793,94776,591950,3824112,25431452,
%T 173453058,1209639642,8604450011,62300851632,458374397312,
%U 3421888118907,25887131596018,198244731603623,1535346218316422,12015325816028313,94944352095728825,757046484552152932,6087537591051072864
%N Number of 1324-avoiding permutations of length n.
%D Miklós Bóna, Combinatorics of Permutations. Discrete Mathematics and its Applications (Boca Raton), 2nd edn. CRC Press, Boca Raton (2012).
%H David Bevan, <a href="/A061552/b061552.txt">Table of n, a(n) for n = 0..50</a> (from the Conway/Guttmann reference; terms 0..31 by Joerg Arndt, taken from the Johansson/Nakamura reference; terms 37..50 by Bjarki Ágúst Guðmundsson, taken from the Conway/Guttmann/Zinn-Justin reference).
%H M. H. Albert, M. Elder, A. Rechnitzer, P. Westcott, and M. Zabrocki, <a href="http://arxiv.org/abs/math/0502504">On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia</a>, arXiv:math/0502504 [math.CO], 2005.
%H R. Arratia, <a href="https://doi.org/10.37236/1477">On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern.</a>, Electron. J. Combin. 6, N1 (1999).
%H David Bevan, <a href="http://arxiv.org/abs/1406.2890">Permutations avoiding 1324 and patterns in Łukasiewicz paths</a>, arXiv:1406.2890 [math.CO], 2014-2015.
%H David Bevan, Robert Brignall, Andrew Elvey Price and Jay Pantone, <a href="https://doi.org/10.1016/j.ejc.2020.103115">A structural characterisation of Av(1324) and new bounds on its growth rate</a>, European J. Combin. 88 (2020).
%H Miklós Bóna, <a href="http://arxiv.org/abs/1207.2379">A new upper bound for 1324-avoiding permutations</a>, arXiv:1207.2379 [math.CO], 2012.
%H Miklós Bóna, <a href="http://dx.doi.org/10.1017/S0963548314000091">A new upper bound for 1324-avoiding permutations</a>, Combin. Probab. Comput. 23(5), 717-724 (2014).
%H Miklós Bóna, <a href="http://arxiv.org/abs/1404.4033">A new record for 1324-avoiding permutations</a>, arXiv:1404.4033 [math.CO], 2014.
%H Miklós Bóna, <a href="http://dx.doi.org/10.1007/s40879-014-0020-6">A new record for 1324-avoiding permutations</a>, European Journal of Mathematics (2015) 1:198-206, DOI 10.1007/s40879-014-0020-6.
%H A. Claesson, V. Jelínek, and E. Steingrímsson, <a href="http://dx.doi.org/10.1016/j.jcta.2012.05.006">Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns</a>. J. Combin. Theory Ser. A 119(8), 1680-1691 (2012).
%H Andrew R. Conway and Anthony J. Guttmann, <a href="http://arxiv.org/abs/1405.6802">On the growth rate of 1324-avoiding permutations</a>, arXiv:1405.6802 [math.CO], (2014).
%H Andrew R. Conway, Anthony J. Guttmann and Paul Zinn-Justin, <a href="https://arxiv.org/abs/1709.01248">1324-avoiding permutations revisited</a>, arXiv preprint arXiv:1709.01248 [math.CO], 2017.
%H Steven Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/csolve/av.pdf">Pattern-Avoiding Permutations</a> [Broken link?]
%H Steven Finch, <a href="/A240885/a240885.pdf">Pattern-Avoiding Permutations</a> [Cached copy, with permission]
%H A. L. L. Gao, S. Kitaev, and P. B. Zhang, <a href="https://arxiv.org/abs/1605.05490">On pattern avoiding indecomposable permutations</a>, arXiv:1605.05490 [math.CO], 2016.
%H Ruth Hoffmann, Özgür Akgün, and Christopher Jefferson, <a href="https://arxiv.org/abs/2311.17581">Composable Constraint Models for Permutation Enumeration</a>, arXiv:2311.17581 [cs.DM], 2023.
%H Fredrik Johansson and Brian Nakamura, <a href="http://arxiv.org/abs/1309.7117">Using functional equations to enumerate 1324-avoiding permutations</a>, arXiv:1309.7117 [math.CO], (2013).
%H A. Marcus and G. Tardos, <a href="http://dx.doi.org/10.1016/j.jcta.2004.04.002">Excluded permutation matrices and the Stanley-Wilf conjecture</a>, J. Combin. Theory Ser. A 107(1), 153-160 (2004).
%H B. K. Nakamura, <a href="https://rucore.libraries.rutgers.edu/rutgers-lib/40633/">Computational methods in permutation patterns</a>, PhD Dissertation, Rutgers University, May 2013.
%H Brian Nakamura and Doron Zeilberger, <a href="http://arxiv.org/abs/1209.2353">Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes</a>, arXiv preprint arXiv:1209.2353 [math.CO], 2012.
%H Anthony Zaleski and Doron Zeilberger, <a href="https://arxiv.org/abs/1712.10072">On the Intriguing Problem of Counting (n+1,n+2)-Core Partitions into Odd Parts</a>, arXiv:1712.10072 [math.CO], 2017.
%e a(4)=23 because all 24 permutations of length 4, except 1324 itself, avoid the pattern 1324.
%p count1324 := proc(n::nonnegint) if (n<4) then return n!; fi; if (n=4) then return 23; fi; return nodes([5,5,5,5], n-5) + nodes([5,3,5,5], n-5) + nodes([5,4,4,5], n-5) + nodes([5,5,4,5], n-5) + nodes([4,3,4], n-5) + nodes([5,3,4,5], n-5); end:
%p nodes := proc(p, h) option remember; local i, j, s, l; if (h=0) then return convert(p, `+`); fi; s := 0; for j to nops(p) do l := p[j]+1; for i from 2 to j do l := l, `min`(j+1, p[i]); od; for i from j+1 to p[j] do l := l, p[i-1]+1; od; s := s+nodes([l], h-1); od; return s; end:
%t a[n_] := n!/;n<4; a[4]=23; a[n_] := Total[nodes[#,n-5]&/@{{4,3,4},{5,3,4,5},{5,3,5,5},{5,4,4,5},{5,5,4,5},{5,5,5,5}}]; nodes[p_,0]:=Total[p]; nodes[p_,h_] := nodes[p,h] = Sum[nodes[Join[{p[[j]]+1}, Min[j+1,#]&/@p[[2;;j]], p[[j;;p[[j]]-1]]+1],h-1], {j,Length[p]}]; Array[a,12] (* _David Bevan_, May 25 2012 *)
%Y A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).
%K nonn
%O 0,3
%A Darko Marinov (marinov(AT)lcs.mit.edu), May 17 2001
%E More terms from _Vincent Vatter_, Feb 26 2005
%E a(23)-a(25) added from the Albert et al. paper by _N. J. A. Sloane_, Mar 29 2013
|
