login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #33 Jan 11 2025 19:54:19

%S 1,14,82,410,1918,8657,38225,166322,716170,3059864,12994936,54924212,

%T 231235054,970347575,4060697955,16952812170,70629116910,293720506860,

%U 1219498444500,5055891511980,20933654593020,86571545598642,357628915621698,1475896409177780

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

%H Vincenzo Librandi, <a href="/A082971/b082971.txt">Table of n, a(n) for n = 4..1000</a>

%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 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 T. Mansour and A. Vainshtein, <a href="https://arxiv.org/abs/math/0105073">Counting occurrences of 132 in a permutation</a>, arXiv:math/0105073 [math.CO], 2001.

%F 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).

%F 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)!) for n>=5; a(4)=1. G.f.: (1/2)*(P(x) + Q(x)/(1-4*x)^(5/2)), where P(x) = 2*x^3 - 5*x^2 + 7*x - 2, Q(x) = -22*x^6 - 106*x^5 + 292*x^4 - 302*x^3 + 135*x^2 - 27*x + 2. - _Emeric Deutsch_, Mar 27 2008

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

%p 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

%t 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)!);

%t Table[a[n], {n, 4, 25}] (* _Jean-François Alcover_, Oct 30 2018 *)

%o (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)

%o (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

%Y Cf. A002054, A082970, A138162, A138163.

%Y Column k=3 of A263771.

%K nonn,easy

%O 4,2

%A _Benoit Cloitre_, May 27 2003

%E Edited by _N. J. A. Sloane_, May 21 2008 at the suggestion of _R. J. Mathar_