文献あり

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

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

Dyck路

二つのベクトル $U ≜ (1, 1)$ と $D ≜ (1, - 1)$ を並べた長さ $2 n$ の列
$\begin{array}{r} ω = (ω_{1}, \dots, ω_{2 n}), ω_{i} \in {U, D} \end{array}$
で，以下の二条件を満たすものをサイズ $n$ のDyck路という．
(条件1) すべての部分和 $ω_{1} + \dots + ω_{i}, 1 \leq i \leq 2 n$ の $y$ 座標が非負である．
(条件2) 最後までの和 $ω_{1} + \dots + ω_{2 n}$ の $y$ 座標が0である．

Dyck路のピーク

Dyck路に含まれる， $U$ と $D$ が連続する部分列 $(U, D)$ をピークという．

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

サイズ $n$ のDyck路のピークのうち一つを， $(U, ∙, D)$ という列に置き換えてできる列を，サイズ $n$ の印付きDyck路という．

本記事で証明するのは以下の内容である．

サイズ $n$ の印付きDyck路は $(\binom{2 n - 1}{n})$ 個存在する．

Narayana多項式と超幾何の和公式を使う証明

ピークを $k$ 個持つサイズ $n$ のDyck路の数は， Narayana数 [2]
$\begin{array}{r} \frac{1}{n} (\binom{n}{k}) (\binom{n}{k - 1}) \end{array}$
であることが知られている．(この事実の証明は例えばStanley [3]に載ってる．)
つまり，Dyck路 $ω$ に対してそのピークの数を $p e a k (ω)$ と書くことにすると，ピークの数に関する母関数を
$\begin{array}{r} f_{n} (x) ≜ \sum_{ω \in {D y c k}_{n}} x^{p e a k (ω)} = \sum_{k = 1}^{n} \frac{1}{n} (\binom{n}{k}) (\binom{n}{k - 1}) x^{k} \end{array}$
と書くことができる．但し，サイズ $n$ のDyck路の集合を ${D y c k}_{n}$ と書いた．この多項式 $f_{n} (x)$ はNarayana多項式と呼ばれる．

今我々が求めたい「サイズ $n$ の印付きDyck路の数」は，式で書くと
$\begin{array}{r} \sum_{ω \in {D y c k}_{n}} p e a k (ω) \end{array}$
なので， $\frac{d}{d x} f (x)$ に $x = 1$ を代入すれば求まる．

以下，
$\begin{array}{r} f_{n}^{'} (1) = \sum_{k = 1}^{n} \frac{k}{n} (\binom{n}{k}) (\binom{n}{k - 1}) \end{array}$
を計算する．式をよく見ると，この式はガウスの超幾何級数 $_{2} F_{1}$ を使って
$\begin{array}{r} f_{n}^{'} (1) =_{2} F_{1} (- n, - n + 1; 1; 1) \end{array}$
と書くことができて，ガウスの超幾何定理 [4]により
$\begin{array}{r} f_{n}^{'} (1) =_{2} F_{1} (- n, - n + 1; 1; 1) = \frac{(2 n - 1)!}{n! (n - 1)!} = (\binom{2 n - 1}{n}) \end{array}$
がわかる．（証明終わり）

補足：「オブジェクトに一箇所印をつけることは母関数の微分に対応する」という発想は，例えばFlajolet [5]により一般的な形で述べられている．

Dyck路に印付きピークを突っ込む証明

筆者が以前の記事 [6]でも述べたように，サイズ $n$ の印付きDyck路は，サイズ $n - 1$ のDyck路の任意の位置に $(U, ∙, D)$ を突っ込んで過不足なく作ることができる．
つまり，サイズ $n$ の印付きDyck路の集合を $M_{n}$ と書くと，全単射
$\begin{array}{r} {D y c k}_{n} \times {0, 1, \dots, 2 n} \to M_{n + 1} \end{array}$
が存在する．よって，
$\begin{array}{r} | M_{n + 1} | = \frac{1}{n + 1} (\binom{2 n}{n}) (2 n + 1) = (\binom{2 n + 1}{n + 1}) . \end{array}$
（証明終わり）