0,5

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

Markus Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. Appl. Math., Vol. 30, No. 4 (2003), 607-632; arXiv preprint, arXiv:math/0112092 [math.CO], 2001-2002.

Toufik Mansour and Alek 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.

John Noonan and Doron Zeilberger, The Enumeration of Permutations with a Prescribed Number of "Forbidden" Patterns, Adv. in Appl. Math., Vol. 17, No. 4 (1996), 381-407; arXiv preprint, arXiv:math/9808080 [math.CO], 1998; MR1422065 (97j:05003).

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

a(n) ~ 59 * 4^(n-1) / (n^(3/2) * sqrt(Pi)). - Amiram Eldar, Oct 05 2025

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

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

{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

(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

(SageMath) [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

Cf. A000108, A003517, A084249, A138159.

Leading column of A229158.

Sequence in context: A305543 A356363 A183900 * A359884 A069515 A206949

Adjacent sequences: A001086 A001087 A001088 * A001090 A001091 A001092

nonn,easy

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

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

approved