指定したx座標にピークを持つDyck路の数はカタラン数
$n$は非負整数とする．二次元平面$\mathbb{R}^2$の二つのベクトル$\mathsf{U}\triangleq(1,1),\mathsf{D}\triangleq(1,-1)$の列
\begin{align}
\omega=(\omega_1,\ldots,\omega_{2n})\qquad \omega_i\in\{\mathsf{U},\mathsf{D}\}
\end{align}
であって，以下の二条件
- 任意の部分和の$y$座標が非負である．つまり
\begin{align} (x_r,y_r)\triangleq\sum_{i=1}^r\omega_i \end{align}
と定義すると$y_r\geq 0\ (r=1,\ldots,2n)$が成り立つ． - $y_{2n}=0$が成り立つ．
を満たすものを，サイズ$n$のDyck路という．
サイズ$n$のDyck路の個数は，カタラン数$C_n\triangleq\frac{1}{n+1}\binom{2n}{n}$であることが知られている．
Dyck路$\omega$に現れる$\mathsf{UD}$という部分列のことを，ピークという．
下の図1を見るとわかりやすいと思う．Dyck路は下図のように図示され，線の高さが極大な場所がピークである．
![サイズ!FORMULA[13][1121089][0]のDyck路!FORMULA[14][1419579614][0]の図示．赤い矢印で示した部分がピーク．](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2FaA8LchbqMcS3bT9L1thO.jpeg?alt=media)
サイズ$10$のDyck路$\mathsf{UUDUUDDDUD}$の図示．赤い矢印で示した部分がピーク．
特定の$x$座標にピークを持つDyck路の数は以下のように求められる．
任意の自然数$n\in\mathbb{N}$と自然数$k\in\{1,\ldots,2n-1\}$が与えられているとする．
サイズ$n$のDyck路$\omega=(\omega_1,\ldots,\omega_{2n})$のうち，$\omega_k=\mathsf{U},\omega_{k+1}=\mathsf{D}$を満たすものは，$C_{n-1}$個存在する．
「サイズ$n-1$のDyck路」と「サイズ$n$で$\omega_k=\mathsf{U},\omega_{k+1}=\mathsf{D}$を満たすDyck路」との全単射を作ればよい．
サイズ$n-1$のDyck路を
\begin{align}
\alpha=(\alpha_1,\ldots,\alpha_{2n-2})
\end{align}
とする．このとき
\begin{align}
\alpha'\triangleq(\alpha_1,\ldots,\alpha_{k-1},\mathsf{U},\mathsf{D},\alpha_{k},\ldots,\alpha_{2n-2})
\end{align}
は，サイズ$n$で$\omega_k=\mathsf{U},\omega_{k+1}=\mathsf{D}$を満たすDyck路である．
対応$\alpha\mapsto\alpha'$は所望の全単射である．
