×

A bijection on Dyck paths and its consequences. (English) Zbl 0890.05005

Discrete Math. 179, No. 1-3, 253-256 (1998); corrigendum ibid. 187, No. 1-3, 297 (1998).
A Dyck path of semilength \(n\) is a path in the first quadrant beginning at \((0,0)\), ending at \((2n,0)\), and consisting of rises (steps of \((1,1)\)) and falls (steps of \((1,-1)\)). This article gives several proofs, one of which uses a bijection, of the fact that there are as many Dyck paths of semilength \(n\) beginning with exactly \(k\) consecutive rises (height of the first peak equals \(k\)) as there are with exactly \(k\) falls landing on the horizontal axis (\(k\) returns). As a consequence of the bijection it is shown that the Narayana numbers \(u(n,k)= \left({1\over n}\right) \left(\begin{smallmatrix} n\\ k\end{smallmatrix}\right) \left(\begin{smallmatrix} n\\ k+1\end{smallmatrix}\right)\) (*), which count Dyck paths of semilength \(n\) with \(k\) valleys (falls followed by rises) also count Dyck paths of semilength \(n\) with \(k\) high peaks (rises to a height of at least 2 followed by falls).
(*) Reviewer’s remark: It would have been helpful if the article had stated which of the references contains this result and had included the figure to which it refers.

MSC:

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

References:

[1] Deutsch, E., Enumeration of Dyck paths according to length and various other parameters (1995), Unsubmitted manuscript
[2] Feller, W., An Introduction to Probability Theory and Its Applications (1968), Wiley: Wiley New York · Zbl 0155.23101
[3] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0836.00001
[4] Kreweras, G., Joint distributions of three descriptive parameters of bridges, (Combinatoire énumérative, Proc. ‘Colloque de combinatoire énumérative’. Combinatoire énumérative, Proc. ‘Colloque de combinatoire énumérative’, Montréal, May 28-June 1, 1985. Combinatoire énumérative, Proc. ‘Colloque de combinatoire énumérative’. Combinatoire énumérative, Proc. ‘Colloque de combinatoire énumérative’, Montréal, May 28-June 1, 1985, Lecture Notes in Mathematics, vol. 1234 (1986), Springer: Springer Berlin), 177-191 · Zbl 0612.05012
[5] Kreweras, G.; Moszkowski, P., A new enumerative property of the Narayana numbers, Statist. Plann. Inference, 14, 63-67 (1986) · Zbl 0601.05005
[6] Kreweras, G.; Poupard, Y., Subdivision des nombres de Narayana suivant deux paramèters supplémentaires, Eur. J. Combin., 7, 141-149 (1986) · Zbl 0647.05007
[7] R.A. Sulanke, Catalan path statistics having the Narayana distribution, Discrete Math., to appear.; R.A. Sulanke, Catalan path statistics having the Narayana distribution, Discrete Math., to appear. · Zbl 0896.05002
[8] R.A. Sulanke, private communication.; R.A. Sulanke, private communication.
[9] Zeilberger, D., Six études in generating functions, Internat. J. Computer Math., 29, 201-215 (1989) · Zbl 0689.05003
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.