login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A138163 Number of permutations of {1,2,...,n} containing exactly 5 occurrences of the pattern 132. 3
5, 55, 394, 2225, 11539, 57064, 273612, 1283621, 5924924, 27005978, 121861262, 545368160, 2423923480, 10710273856, 47085144255, 206085075295, 898489543020, 3903621095130, 16906888008960, 73018012573950, 314540265217362 (list; graph; refs; listen; history; text; internal format)
OFFSET

5,1

REFERENCES

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

LINKS

Table of n, a(n) for n=5..25.

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.

FORMULA

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.

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.

EXAMPLE

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

MAPLE

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);

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 *)

CROSSREFS

Cf. A002054, A082970, A082971, A138162.

Column k=5 of A263771.

Sequence in context: A014852 A144893 A015266 * A306095 A081300 A190543

Adjacent sequences:  A138160 A138161 A138162 * A138164 A138165 A138166

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Mar 28 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 26 05:51 EST 2020. Contains 332277 sequences. (Running on oeis4.)