×

A new enumerative property of the Narayana numbers. (English) Zbl 0601.05005

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 [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 [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.
Reviewer: T.Walsh

MSC:

05A15 Exact enumeration problems, generating functions
Full Text: DOI

References:

[1] Kreweras, G., Sur les éventails de segments, Cashiers du B.U.R.O., 15, 1-41 (1970)
[2] Narayana, T. V., Sur les treillis formés par les partitions d’un entier, C.R. Acad. Sci. Paris Ser. I., 240, 1188 (1955) · Zbl 0064.12705
[3] Riordan, J., Combinatorial Identities, ((1968), Wiley: Wiley New York), 17 · Zbl 0194.00502
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.