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
Keywords
Examples
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
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-8, Adv. 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).
Programs
-
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
-
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
-
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 *) -
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
-
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
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
D-finite with recurrence -(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, equivalent to recurrence of [Noonan-Zeilberger] binomial. - R. J. Mathar, Jan 04 2017
Extensions
Terms a(25) onward added by G. C. Greubel, Sep 19 2019