login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001089 Number of permutations of [n] containing exactly 2 increasing subsequences of length 3. 5
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

LINKS

Table of n, a(n) for n=0..24.

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.

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, [math/9808080] The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns. 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

MATHEMATICA

{0}~Join~CoefficientList[Series[((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), {x, 0, 23}], x] (* or *)

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

CROSSREFS

Cf. A003517, A084249, A138159.

Leading column of A229158.

Sequence in context: A009134 A009137 A183900 * A069515 A206949 A215636

Adjacent sequences:  A001086 A001087 A001088 * A001090 A001091 A001092

KEYWORD

nonn

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 19:36 EST 2018. Contains 299469 sequences. (Running on oeis4.)