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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

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

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.

B. K. Nakamura, Computational methods in permutation patterns, PhD Dissertation, Rutgers University, May 2013.

LINKS

Joerg Arndt, Table of n, a(n) for n = 0..31 (from the Johansson/Nakamura reference).

Fredrik Johansson, Brian Nakamura, Using functional equations to enumerate 1324-avoiding permutations, arXiv:1309.7117 [math.CO], (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

Sequence in context: A004040 A216040 A005802 * A053488 A117106 A137534

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

Content is available under The OEIS End-User License Agreement .

Last modified April 24 05:09 EDT 2014. Contains 240953 sequences.