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

1, 14, 82, 410, 1918, 8657, 38225, 166322, 716170, 3059864, 12994936, 54924212, 231235054, 970347575, 4060697955, 16952812170, 70629116910, 293720506860, 1219498444500, 5055891511980, 20933654593020, 86571545598642, 357628915621698, 1475896409177780

Offset

4,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 4..1000

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) = (2*n-9)!/n!/6/(n-5)! *(n^6+51*n^5-407*n^4-99*n^3 +7750*n^2 -22416*n +20160).

a(n) = (n^6 + 51n^5 - 407n^4 - 99n^3 + 7750n^2 - 22416n + 20160)(2n-9)!/[6 n!(n-5)! for n>=5; a(4)=1. G.f.=(1/2)(P(x) + Q(x)/(1-4x)^(5/2), where P(x)=2x^3 - 5x^2 + 7x - 2, Q(x)=-22x^6 - 106x^5 + 292x^4 - 302x^3 + 135x^2 - 27x + 2. - Emeric Deutsch, Mar 27 2008

Example

a(4)=1 because we have 1432 (the 132 occurrences are 143, 142 and 132).

Maple

P:=2*x^3-5*x^2+7*x-2: Q:=-22*x^6-106*x^5+292*x^4-302*x^3+135*x^2-27*x+2: g:= (P+Q/(1-4*x)^(5/2))*1/2: gser:=series(g, x=0, 30): seq(coeff(gser, x, n), n=4..25); # Emeric Deutsch, Mar 27 2008

Mathematica

a[4] = 1; a[n_] := (n^6 + 51 n^5 - 407 n^4 - 99 n^3 + 7750 n^2 - 22416 n + 20160) (2 n - 9)!/(6 n! (n - 5)!);
Table[a[n], {n, 4, 25}] (* Jean-François Alcover, Oct 30 2018 *)

Prog

(PARI) a(n)=(2*n-9)!/n!/6/(n-5)!*(n^6+51*n^5-407*n^4-99*n^3 +7750*n^2 -22416*n+20160)
(Magma) [1] cat [(n^6+51*n^5-407*n^4-99*n^3+7750*n^2-22416*n+20160)* Factorial(2*n-9)/(6*Factorial(n)*Factorial(n-5)): n in [5..30]]; // Vincenzo Librandi, Oct 30 2018

Crossrefs

Cf. A002054, A082970, A138162, A138163.

Column k=3 of A263771.

Sequence in context: A209942 A215700 A199912 * A176010 A250562 A166819

Adjacent sequences: A082968 A082969 A082970 * A082972 A082973 A082974

Keyword

nonn

Author

Benoit Cloitre, May 27 2003

Extensions

Edited by N. J. A. Sloane, May 21 2008 at the suggestion of R. J. Mathar

Status

approved