login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061552 Number of 1324-avoiding permutations of length n. 14
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
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.
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.
EXAMPLE
a(4)=23 because all 24 permutations of length 4, except 1324 itself, avoid the pattern 1324.
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 *)
CROSSREFS
A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).
Sequence in context: A004040 A216040 A005802 * A338752 A263778 A352854
KEYWORD
nonn
AUTHOR
Darko Marinov (marinov(AT)lcs.mit.edu), May 17 2001
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
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 07:14 EDT 2024. Contains 370954 sequences. (Running on oeis4.)