1
大学数学基礎解説
文献あり

ピークに印をつけたDyck路の数:さらに二通りの証明

87
1
$$$$

サイズ$n$のDyck路のピークに一箇所印を付けたオブジェクトの総数は$\binom{2n-1}{n}$通りある.
この事実に関して,例えば OddieさんのMathlog記事 [1]に全単射的証明が載っている.
この記事では,もう二種類の証明 (超幾何の和公式による証明,上記とは別の組合せ論的考察に基づく証明)をつける.

Dyck路

二つのベクトル$\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路のピーク

Dyck路に含まれる,$\mathsf{U}$$\mathsf{D}$が連続する部分列$(\mathsf{U,D})$をピークという.

ピークに一箇所印をつけたDyck路

サイズ$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}
(証明終わり)

参考文献

投稿日:2023614
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

Do everything bijectively.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中