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.
(*) 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.
Reviewer: T.R.Walsh (Montreal)
MSC:
05A15 | Exact enumeration problems, generating functions |
Online Encyclopedia of Integer Sequences:
Signature-permutation of a Catalan Automorphism: Deutsch’s 1998 bijection on Dyck paths.Signature-permutation of the inverse of Deutsch’s 1998 bijection on Dyck paths.
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.