ピークに印をつけたDyck路の数：さらに二通りの証明
サイズ$n$のDyck路のピークに一箇所印を付けたオブジェクトの総数は$\binom{2n-1}{n}$通りある．
この事実に関して，例えば
OddieさんのMathlog記事
[1]に全単射的証明が載っている．
この記事では，もう二種類の証明 (超幾何の和公式による証明，上記とは別の組合せ論的考察に基づく証明)をつける．
二つのベクトル$\mathsf{U}\triangleq(1,1)$と$\mathsf{D}\triangleq(1,-1)$を並べた長さ$2n$の列
\begin{align}
\omega=(\omega_1,\ldots,\omega_{2n}),\quad
\omega_i\in\{\mathsf{U},\mathsf{D}\}
\end{align}
で，以下の二条件を満たすものをサイズ$n$のDyck路という．
(条件1) すべての部分和$\omega_1+\ldots+\omega_i,\quad 1\leq i\leq 2n$の$y$座標が非負である．
(条件2) 最後までの和$\omega_1+\ldots+\omega_{2n}$の$y$座標が0である．
Dyck路に含まれる，$\mathsf{U}$と$\mathsf{D}$が連続する部分列$(\mathsf{U,D})$をピークという．
サイズ$n$のDyck路のピークのうち一つを，$(\mathsf{U},\bullet,\mathsf{D})$という列に置き換えてできる列を，サイズ$n$の印付きDyck路という．
本記事で証明するのは以下の内容である．
サイズ$n$の印付きDyck路は$\binom{2n-1}{n}$個存在する．
Narayana多項式と超幾何の和公式を使う証明
ピークを$k$個持つサイズ$n$のDyck路の数は，
Narayana数
[2]
\begin{align}
\frac{1}{n}\binom{n}{k}\binom{n}{k-1}
\end{align}
であることが知られている．(この事実の証明は例えばStanley [3]に載ってる．)
つまり，Dyck路$\omega$に対してそのピークの数を${\rm peak}(\omega)$と書くことにすると，ピークの数に関する母関数を
\begin{align}
f_n(x)\triangleq\sum_{\omega\in{\rm Dyck}_n}x^{{\rm peak}(\omega)}=
\sum_{k=1}^n
\frac{1}{n}\binom{n}{k}\binom{n}{k-1}x^k
\end{align}
と書くことができる．但し，サイズ$n$のDyck路の集合を${\rm Dyck}_n$と書いた．この多項式$f_n(x)$はNarayana多項式と呼ばれる．
今我々が求めたい「サイズ$n$の印付きDyck路の数」は，式で書くと
\begin{align}
\sum_{\omega\in{\rm Dyck}_n}{\rm peak}(\omega)
\end{align}
なので，$\frac{d}{dx}f(x)$に$x=1$を代入すれば求まる．
以下，
\begin{align}
f'_n(1)=\sum_{k=1}^n\frac{k}{n}\binom{n}{k}\binom{n}{k-1}
\end{align}
を計算する．式をよく見ると，この式はガウスの超幾何級数$_2F_1$を使って
\begin{align}
f'_n(1)={}_2F_1(-n,-n+1;1;1)
\end{align}
と書くことができて，
ガウスの超幾何定理
[4]により
\begin{align}
f'_n(1)={}_2F_1(-n,-n+1;1;1)=\frac{(2n-1)!}{n!(n-1)!}=\binom{2n-1}{n}
\end{align}
がわかる．（証明終わり）
補足：「オブジェクトに一箇所印をつけることは母関数の微分に対応する」という発想は，例えばFlajolet [5]により一般的な形で述べられている．
Dyck路に印付きピークを突っ込む証明
筆者が
以前の記事
[6]でも述べたように，サイズ$n$の印付きDyck路は，サイズ$n-1$のDyck路の任意の位置に$(\mathsf{U},\bullet,\mathsf{D})$を突っ込んで過不足なく作ることができる．
つまり，サイズ$n$の印付きDyck路の集合を$M_n$と書くと，全単射
\begin{align}
{\rm Dyck}_{n}\times\{0,1,\ldots,2n\}\to M_{n+1}
\end{align}
が存在する．よって，
\begin{align}
|M_{n+1}|=\frac{1}{n+1}\binom{2n}{n}(2n+1)=\binom{2n+1}{n+1}.
\end{align}
（証明終わり）