A061552 Number of 1324-avoiding permutations of length n.

1, 1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, 3824112, 25431452, 173453058, 1209639642, 8604450011, 62300851632, 458374397312, 3421888118907, 25887131596018, 198244731603623, 1535346218316422, 12015325816028313, 94944352095728825, 757046484552152932, 6087537591051072864

Offset: 0

Author

Darko Marinov (marinov(AT)lcs.mit.edu), May 17 2001

Keywords

• nonn

Examples

			a(4)=23 because all 24 permutations of length 4, except 1324 itself, avoid the pattern 1324.
		

References

• Miklós Bóna, Combinatorics of Permutations. Discrete Mathematics and its Applications (Boca Raton), 2nd edn. CRC Press, Boca Raton (2012).

Links

• David Bevan, Table of n, a(n) for n = 0..50 (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).
• M. H. Albert, M. Elder, A. Rechnitzer, P. Westcott, and M. Zabrocki, On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia, arXiv:math/0502504 [math.CO], 2005.
• R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern., Electron. J. Combin. 6, N1 (1999).
• David Bevan, Permutations avoiding 1324 and patterns in Łukasiewicz paths, arXiv:1406.2890 [math.CO], 2014-2015.
• David Bevan, Robert Brignall, Andrew Elvey Price and Jay Pantone, A structural characterisation of Av(1324) and new bounds on its growth rate, European J. Combin. 88 (2020).
• Miklós Bóna, A new upper bound for 1324-avoiding permutations, arXiv:1207.2379 [math.CO], 2012.
• Miklós Bóna, A new upper bound for 1324-avoiding permutations, Combin. Probab. Comput. 23(5), 717-724 (2014).
• Miklós Bóna, A new record for 1324-avoiding permutations, arXiv:1404.4033 [math.CO], 2014.
• Miklós Bóna, A new record for 1324-avoiding permutations, European Journal of Mathematics (2015) 1:198-206, DOI 10.1007/s40879-014-0020-6.
• A. Claesson, V. Jelínek, and E. Steingrímsson, Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns. J. Combin. Theory Ser. A 119(8), 1680-1691 (2012).
• Andrew R. Conway and Anthony J. Guttmann, On the growth rate of 1324-avoiding permutations, arXiv:1405.6802 [math.CO], (2014).
• Andrew R. Conway, Anthony J. Guttmann and Paul Zinn-Justin, 1324-avoiding permutations revisited, arXiv preprint arXiv:1709.01248 [math.CO], 2017.
• Steven Finch, Pattern-Avoiding Permutations [Broken link?]
• Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
• A. L. L. Gao, S. Kitaev, and P. B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
• Ruth Hoffmann, Özgür Akgün, and Christopher Jefferson, Composable Constraint Models for Permutation Enumeration, arXiv:2311.17581 [cs.DM], 2023.
• Fredrik Johansson and Brian Nakamura, Using functional equations to enumerate 1324-avoiding permutations, arXiv:1309.7117 [math.CO], (2013).
• A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107(1), 153-160 (2004).
• B. K. Nakamura, Computational methods in permutation patterns, PhD Dissertation, Rutgers University, May 2013.
• Brian Nakamura and Doron Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes, arXiv preprint arXiv:1209.2353 [math.CO], 2012.
• Anthony Zaleski and Doron Zeilberger, On the Intriguing Problem of Counting (n+1,n+2)-Core Partitions into Odd Parts, arXiv:1712.10072 [math.CO], 2017.

Crossrefs

A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).

Programs

Maple

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:
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:

Mathematica

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 *)

Extensions

More terms from Vincent Vatter, Feb 26 2005

a(23)-a(25) added from the Albert et al. paper by N. J. A. Sloane, Mar 29 2013