The number of permutations containing exactly one increasing subsequence of length three

✍ Scribed by John Noonan

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 287 KB
• Volume: 152
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00247-t

✦ Synopsis

It is proved that the number of permuations on {I, 2, ... , n} with exactly one increasing subsequence of length 3 is ~(ntn3) [0,0,1,6,27,110,429, ... (Sloane A3517)].

Given a permutaion a E Sn, an abc subsequence is a set of three elements, a(i), aU), a(k), with a(i) < aU) < a(k) and i < j < k. It is known [2][3][4] that the number of permutations on {I, 2, ... , n} with no abc subsequences is given by the Catalan number 1/(n + 1)(~n). A natural question is: is there a nice expression for the generating function L~~~0 B(n, r)qr, where B(n, r) is the number of permutations on {I, 2, ... , n} with exactly r abc's, for 1 ~r ~m? Another question is, for a fixed r, what can one say about the sequence in n, B(n, r)? Doron Zeilberger conjectures that for any given r, the coefficients B(n, r) of the generating function are P-recursive in n, i.e. they satisfy a linear recurrence with polynomial coefficients. This is supported by the fact that