A new enumerative property of the Narayana numbers (Q1080851): Difference between revisions

The Narayana numbers \[ u(k,j)=\frac{1}{k}\left( \begin{matrix} k\\ j\end{matrix} \right)\left( \begin{matrix} k\\ j-1\end{matrix} \right) \] appear in [\textit{T. V. Narayana}, ''Sur les treillis formés par les partitions d'un entier'', C. R. Acad. Sci., Paris 240, 1188-1189 (1955; Zbl 0064.127)]. The sum \(\sum^{k}_{j=1}u(k,j)=\left( \begin{matrix} 2k\\ k\end{matrix} \right)/(k+1)\); this Catalan number is the number of balanced parenthesis systems on 2k parentheses, or ''k-bridges'', as they are called in this paper (a 1970 paper by one of the authors is cited for this piece of folklore, but see, for instance, an ingenious proof in [\textit{D. Tamari}, ''The algebra of bracketings and their enumeration'', Nieuw Arch. Wiskd., III. Ser. 10, 131-146 (1962; Zbl 0109.245)]). A k-bridge consists of j runs of opening parentheses (''jumps''), each followed by a run of closing parentheses (''landings''), for some \(j=1,2,...,k\); and, according to the abstract, it is ''known'' (but no reference is given) that there are u(k,j) k-bridges with j jumps and j landings. In this paper it is shown that u(k,j) is also the number of k-bridges with a total of j-1 runs (jumps or landings), not counting the final landing, which are at least two parentheses long.