A001089 Number of permutations of [n] containing exactly 2 increasing subsequences of length 3.

0, 0, 0, 0, 3, 24, 133, 635, 2807, 11864, 48756, 196707, 783750, 3095708, 12152855, 47500635, 185082495, 719559600, 2793121080, 10830450780, 41965864794, 162539516448, 629399492330, 2437072038302, 9437097796918

Offset

0,5

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

M. Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, arXiv:math/0112092 [math.CO], 2001-2002. Also doi:10.1016/S0196-8858(02)00501-8Adv. Appl. Math., 30, 2003, 607-632.

T. Mansour and A. Vainshtein, Counting occurrences of 123 in a permutation, arXiv:math/0105073 [math.CO], 2001.

Toufik Mansour, Sherry H. F. Yan and Laura L. M. Yang, Counting occurrences of 231 in an involution, Discrete Mathematics 306 (2006), pages 564-572.

J. Noonan and D. Zeilberger, The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns, arXiv:math/9808080 [math.CO], 1998. Also doi:10.1006/aama.1996.0016, Adv. in Appl. Math. 17 (1996), no. 4, 381--407. MR1422065 (97j:05003).

Formula

Noonan and Zeilberger conjectured that a(n) = ((59*n^2+117*n+100)/(2*n*(2*n-1)*(n+5)))*binomial(2*n,n-4). This was proved by Fulmek.

G.f.: ((x^5 -3*x^4 +5*x^3 -10*x^2 +6*x -1)*(1-4*x)^(1/2) - 5*x^5 +7*x^4 -17*x^3 +20*x^2 -8*x +1)/(2*x^6). - Mark van Hoeij, Oct 25 2011

G.f.: x^5*C(x)^11 + 3*x^3*C(x)^8, where C(x) is g.f. for the Catalan numbers (A000108). - Michael D. Weiner, Sep 02 2016

Conjecture: -(n+5)*(n-4)*(59*n^2-n+42)*a(n) +2*(n-1)*(2*n-3)*(59*n^2 +117*n+100)*a(n-1) = 0. - R. J. Mathar, Jan 04 2017

Example

For n=4, there are 4! = 24 permutations of 1234. The identity permutation 1234 has four increasing subsequences of length 3 (123, 124, 134, and 234), and the permutation 2314 has only one increasing subsequence of length 3 (234). Only the permutations 1243, 1324, and 2134 have exactly two increasing subsequences of length 3, and since there are three of them, a(4) = 3. - Michael B. Porter, Sep 03 2016

Maple

seq(`if`(n=0, 0, (100+117*n+59*n^2)*binomial(2*n, n-4)/(2*n*(2*n-1)*(n+5))), n = 0..30); # G. C. Greubel, Sep 19 2019

Mathematica

{0}~Join~CoefficientList[Series[((x^5-3x^4+5x^3-10x^2+6*x-1)(1-4x)^(1/2) - 5x^5+7x^4-17x^3+20x^2-8*x+1)/(2x^6), {x, 0, 23}], x] (* or *)
{0}~Join~CoefficientList[Series[x^5*((1-(1-4x)^(1/2))/(2x))^11 +3x^3*( (1-(1-4x)^(1/2))/(2x))^8, {x, 0, 23}], x] (* Michael De Vlieger, Sep 03 2016 *)

Prog

(PARI) a(n) = (100+117*n+59*n^2)*binomial(2*n, n-4)/(2*n*(2*n-1)*(n+5)) \\ G. C. Greubel, Sep 19 2019
(Magma) [0, 0, 0, 0] cat [(100+117*n+59*n^2)*Binomial(2*n, n-4)/(2*n*(2*n-1)*(n+5)): n in [4..30]]; // G. C. Greubel, Sep 19 2019
(Sage) [0, 0, 0, 0]+[(100+117*n+59*n^2)*binomial(2*n, n-4)/(2*n*(2*n-1)*(n+5)) for n in (4..30)] # G. C. Greubel, Sep 19 2019
(GAP) Concatenation([0, 0, 0, 0], List([4..30], n-> (100+117*n+59*n^2)* Binomial(2*n, n-4)/(2*n*(2*n-1)*(n+5)))); # G. C. Greubel, Sep 19 2019

Crossrefs

Cf. A003517, A084249, A138159.

Leading column of A229158.

Sequence in context: A305543 A356363 A183900 * A359884 A069515 A206949

Adjacent sequences: A001086 A001087 A001088 * A001090 A001091 A001092

Keyword

nonn

Author

John Thomas Noonan [ noonan(AT)euclid.math.temple.edu ]

Extensions

Terms a(25) onward added by G. C. Greubel, Sep 19 2019

Status

approved