|
%I #48 Sep 08 2022 08:44:28
%S 0,0,0,0,3,24,133,635,2807,11864,48756,196707,783750,3095708,12152855,
%T 47500635,185082495,719559600,2793121080,10830450780,41965864794,
%U 162539516448,629399492330,2437072038302,9437097796918
%N Number of permutations of [n] containing exactly 2 increasing subsequences of length 3.
%H G. C. Greubel, <a href="/A001089/b001089.txt">Table of n, a(n) for n = 0..1000</a>
%H M. Fulmek, <a href="https://arxiv.org/abs/math/0112092">Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three</a>, arXiv:math/0112092 [math.CO], 2001-2002. Also <a href="http://dx.doi.org/10.1016/S0196-8858(02)00501-8">doi:10.1016/S0196-8858(02)00501-8</a>Adv. Appl. Math., 30, 2003, 607-632.
%H T. Mansour and A. Vainshtein, <a href="https://arxiv.org/abs/math/0105073">Counting occurrences of 123 in a permutation</a>, arXiv:math/0105073 [math.CO], 2001.
%H Toufik Mansour, Sherry H. F. Yan and Laura L. M. Yang, <a href="http://dx.doi.org/10.1016/j.disc.2006.01.011">Counting occurrences of 231 in an involution</a>, Discrete Mathematics 306 (2006), pages 564-572.
%H J. Noonan and D. Zeilberger, <a href="https://arxiv.org/abs/math/9808080">The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns</a>, arXiv:math/9808080 [math.CO], 1998. Also <a href="http://dx.doi.org/10.1006/aama.1996.0016">doi:10.1006/aama.1996.0016</a>, Adv. in Appl. Math. 17 (1996), no. 4, 381--407. MR1422065 (97j:05003).
%F 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.
%F 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
%F 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
%F 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
%e 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
%p 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
%t {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 *)
%t {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 *)
%o (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
%o (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
%o (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
%o (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
%Y Cf. A003517, A084249, A138159.
%Y Leading column of A229158.
%K nonn
%O 0,5
%A John Thomas Noonan [ noonan(AT)euclid.math.temple.edu ]
%E Terms a(25) onward added by _G. C. Greubel_, Sep 19 2019
|
