A bijection for some paths on the slit plane (Q5933432): Difference between revisions

Let \(P\) be the set of paths in \(\mathbb{Z}\times \mathbb{Z}\) consisting of north steps \((0,1)\), east steps \((1,0)\), south steps \((0,-1)\) and west steps \((-1,0)\) beginning at \((-1,0)\) and ending at \((0,0)\) without touching or crossing the nonnegative \(x\)-axis before they reach their endpoint. A path in \(P\) must have an odd number of steps; so let \(P_{2k+1}\) be the set of paths in \(P\) having \(2k+1\) steps. In [\textit{M. Bousquet-Mélou} and \textit{G. Schaeffer}, Counting paths on the slit plane, preprint], it was shown that \(|P_{2k+1}|= C_{2k+1}\), where \(C_n\) is the \(n\)th Catalan number \({1\over n+1}\left(\begin{smallmatrix} 2n\\ n\end{smallmatrix}\right)\). The article under review establishes a bijection between \(P_{2k+1}\) and the set of 2-coloured Motzkin paths of length \(2k\). Since there are \(C_{n+1}\) 2-coloured Motzkin paths of length \(n\) [\textit{R. P. Stanley}, ``Enumerative combinatoris'', Vol. 2 (Cambridge University Press, Cambridge, U.K.) (1999; Zbl 0978.05002)], the bijection established represents a bijective proof of the result in [\textit{M. Bousquet-Mélou} and \textit{G. Schaeffer} (loc. cit.)].