A220903 Number of permutations of n letters in the class Av_n(213;2).

5, 16, 68, 392, 2905, 25508, 251188, 2703440, 31462590, 393962080, 5289624824, 75921813328, 1161309733909, 18873565250876, 324948587103540, 5910550393881120, 113284096799562930, 2282403914428653360, 48231478277117432040, 1066811449438992210000

Offset

3,1

Links

Vaclav Kotesovec, Table of n, a(n) for n = 3..400

Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908, 2012 (see Prop. 8).

Formula

Recurrence (for n>=6): (n-3)*(n+1)*(n^2 - 8*n + 10)*a(n) = (2*n^5 - 19*n^4 + 38*n^3 + 45*n^2 - 174*n + 120)*a(n-1) - (n-1)*(n^5 - 5*n^4 - 35*n^3 + 249*n^2 - 462*n + 240)*a(n-2) + 2*(n-4)*(n-2)*(n-1)*(2*n - 5)*(n^2 - 6*n + 3)*a(n-3). - Vaclav Kotesovec, Mar 20 2014

a(n) ~ n! * (1 - 2*exp(2)*BesselI(1,2)/n^2). - Vaclav Kotesovec, Mar 26 2014

Mathematica

RecurrenceTable[{2 (-4+n) (-2+n) (-1+n) (-5+2 n) (3-6 n+n^2) a[-3+n]-(-1+n) (240-462 n+249 n^2-35 n^3-5 n^4+n^5) a[-2+n]+(120-174 n+45 n^2+38 n^3-19 n^4+2 n^5) a[-1+n]-(-3+n) (1+n) (10-8 n+n^2) a[n]==0, a[3]==5, a[4]==16, a[5]==68}, a, {n, 3, 20}] (* Vaclav Kotesovec, Mar 26 2014 *)

Prog

(PARI)
catalan(n) = {binomial(2*n, n)/(n+1); }
a(n) = { n! - (2*(n-2)!*sum(i=1, n-4, catalan(i)/(i-1)!)+ 2*(n-2)*(n-3)*catalan(n-3)+ 2*(n-2)*catalan(n-2)-catalan(n)+2*catalan(n-1)); }
\\ Michel Marcus, Feb 07 2013

Crossrefs

Sequence in context: A166932 A027105 A254203 * A042087 A332470 A151465

Adjacent sequences: A220900 A220901 A220902 * A220904 A220905 A220906

Keyword

nonn

Author

N. J. A. Sloane, Jan 01 2013

Extensions

More terms from Michel Marcus, Feb 07 2013

Status

approved