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

5, 55, 394, 2225, 11539, 57064, 273612, 1283621, 5924924, 27005978, 121861262, 545368160, 2423923480, 10710273856, 47085144255, 206085075295, 898489543020, 3903621095130, 16906888008960, 73018012573950, 314540265217362

Offset: 5

Author

Emeric Deutsch, Mar 28 2008

Keywords

• nonn

Examples

			a(5)=5 because we have 13542, 14532, 15243, 15342 and 15423.
		

References

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

Links

• Miklós Bóna, Permutations with one or two 132-subsequences, Discrete Math., 181 (1998) 267-274.
• 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.
• T. Mansour and A. Vainshtein, Counting occurrences of 132 in a permutation, arXiv:math/0105073 [math.CO], 2001.
• B. Nakamura, Approaches for enumerating permutations with a prescribed number of occurrences of patterns, PU. M. A. Vol. 24 2013 No 2, pp. 179-194.

Crossrefs

Cf. A002054, A082970, A082971, A138162.

Column k=5 of A263771.

Programs

Maple

a:=proc(n) options operator, arrow: (1/120)*(n^12+170*n^11 +1861*n^10 -88090*n^9 -307617*n^8 [phone]*n^7 -348117457*n^6 [phone]*n^5 -6970280884*n^4 [phone]*n^3 [phone]*n^2 -30327454080*n [phone]) *factorial(2*n-15) / (factorial(n)*factorial(n-7)) end proc: 5, 55, 394, seq(a(n), n = 8 .. 25);

Mathematica

terms = 21; offset = 5;
P[x_] := 14 x^5 - 17 x^4 + x^3 - 16 x^2 + 14 x - 2;
Q[x_] := -50 x^11 - 2568 x^10 - 10826 x^9 + 16252 x^8 - 12466 x^7 + 16184 x^6 - 16480 x^5 + 9191 x^4 - 2893 x^3 + 520 x^2 - 50 x + 2;
Drop[CoefficientList[(1/2) (P[x] + Q[x]/(1 - 4 x)^(9/2)) + O[x]^(terms + offset), x], offset] (* Jean-François Alcover, Dec 13 2017 *)

Formula

a(n) = (n^12+170n^11+1861n^10-88090n^9-307617n^8+27882510n^7 -348117457n^6 [phone]n^5 -6970280884n^4 [phone]n^3 [phone]n^2 -30327454080n [phone])(2n-15)!/[120 n!(n-7)! ] for n>=8; a(5)=5; a(6)=55; a(7)=394.

G.f.: (1/2)[P(x) + Q(x)/(1-4x)^(9/2)], where P(x) = 14x^5 - 17x^4 + x^3 - 16x^2 + 14x - 2, Q(x)= -50x^11 - 2568x^10 - 10826x^9 + 16252x^8 - 12466x^7 + 16184x^6 - 16480x^5 + 9191x^4 - 2893x^3 + 520x^2 - 50x + 2.