login
A138162
Number of permutations of {1,2,...,n} containing exactly 4 occurrences of the 132 pattern.
3
12, 96, 526, 2593, 12165, 55482, 248509, 1099255, 4817998, 20968680, 90747564, 390927869, 1677551078, 7174848666, 30598014925, 130155932685, 552386655300, 2339526458640, 9890067346740, 41737405295250, 175859194700958
OFFSET
5,1
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.
FORMULA
a(n) = (n^9+102n^8-282n^7-12264n^6+32589n^5+891978n^4-7589428n^3 +25452024n^2-39821760n +23950080)(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.
EXAMPLE
a(5)=12 because we have 12534, 12453, 14253, 14523, 13254, 13524, 15324, 14352, 31542, 21534, 21453 and 25143.
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);
CROSSREFS
Column k=4 of A263771.
Sequence in context: A341233 A120658 A121627 * A264418 A073392 A038845
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Mar 27 2008
STATUS
approved