A138162 Number of permutations of {1,2,...,n} containing exactly 4 occurrences of the 132 pattern.

12, 96, 526, 2593, 12165, 55482, 248509, 1099255, 4817998, 20968680, 90747564, 390927869, 1677551078, 7174848666, 30598014925, 130155932685, 552386655300, 2339526458640, 9890067346740, 41737405295250, 175859194700958

Offset: 5

Author

Emeric Deutsch, Mar 27 2008

Keywords

• nonn

Examples

			a(5)=12 because we have 12534, 12453, 14253, 14523, 13254, 13524, 15324, 14352, 31542, 21534, 21453 and 25143.
		

Links

• Miklós Bóna, The Number of Permutations with Exactly r 132-Subsequences Is P-Recursive in the Size!, Advances in Applied Mathematics, Volume 18, Issue 4, May 1997, Pages 510-522.
• Miklós Bóna, Permutations with one or two 132-subsequences, Discrete Math., 181 (1998) 267-274.
• T. Mansour and A. Vainshtein, Counting occurrences of 132 in a permutation, arXiv:math/0105073 [math.CO], 2001.

Crossrefs

Cf. A002054, A082970, A082971, A138163.

Column k=4 of A263771.

Programs

Maple

P:=5*x^4-7*x^3+2*x^2+8*x-3: Q:=2*x^9+218*x^8+1074*x^7-1754*x^6 +388*x^5 +1087*x^4-945*x^3+320*x^2-50*x+3: g:=(P+Q/(1-4*x)^(7/2))*1/2: gser:=series(g,x=0,30): seq(coeff(gser,x,n),n=5..25);

Formula

a(n) = (n^9+102n^8-282n^7-12264n^6+32589n^5+891978n^4-7589428n^3 [phone]n^2-39821760n [phone])(2n-12)!/[24n!(n-6)! ] for n>=6, a(5)=12.

G.f.: (1/2)[P(x) + Q(x)/(1-4x)^(7/2)], where P(x)=5x^4-7x^3+2x^2+8x-3, Q(x)=2x^9 +218x^8+1074x^7 -1754x^6 +388x^5 +1087x^4 -945x^3+320x^2-50x+3.