The number of permutations containing exactly one increasing subsequence of length three (Q1917505): Difference between revisions

Let \(B(n, r)\) denote the number of permutations of \(n\) elements with exactly \(r\) increasing three-subsequences. (Such a subsequence consists of three elements \(i< j< k\) such that \(\sigma(i)< \sigma(j) < \sigma(k)\).) D. Zeilberger conjectured that for any fixed \(r\) these numbers are \(P\)-recursive in \(n\) (that is they satisfy a linear recurrence with polynomial coefficients). The answer for this conjecture was known affirmative for \(r= 0\) since \(B(n, 0)\) is the \(n\)th Catalan number (and therefore satisfies a first-order recurrence). This paper proves the conjecture for \(r= 1\) providing the closed formula \(B(n, 1)= {3\over n}(\begin{smallmatrix} 2n\\ n+ 3\end{smallmatrix})\).