|
%I #22 Dec 13 2017 10:31:03
%S 5,55,394,2225,11539,57064,273612,1283621,5924924,27005978,121861262,
%T 545368160,2423923480,10710273856,47085144255,206085075295,
%U 898489543020,3903621095130,16906888008960,73018012573950,314540265217362
%N Number of permutations of {1,2,...,n} containing exactly 5 occurrences of the pattern 132.
%D B. K. Nakamura, Computational methods in permutation patterns, PhD Dissertation, Rutgers University, May 2013.
%H Miklós Bóna, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00062-9">Permutations with one or two 132-subsequences</a>, Discrete Math., 181 (1998) 267-274.
%H Miklós Bóna, <a href="http://dx.doi.org/10.1006/aama.1997.0528">The Number of Permutations with Exactly r 132-Subsequences Is P-Recursive in the Size!</a>, Advances in Applied Mathematics, Volume 18, Issue 4, May 1997, Pages 510-522.
%H T. Mansour and A. Vainshtein, <a href="http://arXiv.org/abs/math.CO/0105073">Counting occurrences of 132 in a permutation</a>, arXiv:math/0105073 [math.CO], 2001.
%H B. Nakamura, <a href="http://puma.dimai.unifi.it/24_2/nakamura.pdf">Approaches for enumerating permutations with a prescribed number of occurrences of patterns</a>, PU. M. A. Vol. 24 2013 No 2, pp. 179-194.
%F a(n) = (n^12+170n^11+1861n^10-88090n^9-307617n^8+27882510n^7 -348117457n^6 +2119611370n^5 -6970280884n^4 +10530947320n^3 +2614396896n^2 -30327454080n +29059430400)(2n-15)!/[120 n!(n-7)! ] for n>=8; a(5)=5; a(6)=55; a(7)=394.
%F 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.
%e a(5)=5 because we have 13542, 14532, 15243, 15342 and 15423.
%p a:=proc(n) options operator, arrow: (1/120)*(n^12+170*n^11 +1861*n^10 -88090*n^9 -307617*n^8 +27882510*n^7 -348117457*n^6 +2119611370*n^5 -6970280884*n^4 +10530947320*n^3 +2614396896*n^2 -30327454080*n +29059430400) *factorial(2*n-15) / (factorial(n)*factorial(n-7)) end proc: 5, 55, 394, seq(a(n), n = 8 .. 25);
%t terms = 21; offset = 5;
%t P[x_] := 14 x^5 - 17 x^4 + x^3 - 16 x^2 + 14 x - 2;
%t 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;
%t 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 *)
%Y Cf. A002054, A082970, A082971, A138162.
%Y Column k=5 of A263771.
%K nonn
%O 5,1
%A _Emeric Deutsch_, Mar 28 2008
| 