login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061552 Number of 1324-avoiding permutations of length n. 9
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

Bóna, M.: 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..36 (from the Conway/Guttmann reference; terms 0..31 by Joerg Arndt, taken from the Johansson/Nakamura reference).

M. H. Albert, M. Elder, A. Rechnitzer, P. Westcott, M. Zabrocki, On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia, arXiv:math.CO/0502504, 2005.

R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin. 6, N1 (1999).

D. Bevan, Permutations avoiding 1324 and patterns in Łukasiewicz paths, arXiv:1406.2890 [math.CO], 2014-2015.

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

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, 2012.

EXAMPLE

a(4)=23 because all 24 permutations of length 4, except 1324 itself, avoid 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 * A263778 A053488 A117106

Adjacent sequences:  A061549 A061550 A061551 * A061553 A061554 A061555

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 10 11:50 EST 2016. Contains 279001 sequences.