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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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

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.

Andrew R. Conway and Anthony J. Guttmann, On the growth rate of 1324-avoiding permutations, arXiv:1405.6802 [math.CO], (2014).

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.

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

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 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 | 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 December 21 10:46 EST 2014. Contains 252305 sequences.