デラノイ数に関するメモ

デラノイ数って?

D(n,m):= (0,0)から(n,m)まで次の3つの移動方法を使って移動する方法の通り数

  • (x,y) から (x+1, y) (以降「縦」と表現)
  • (x,y) から (x, y+1) (以降「横」と表現)
  • (x,y) から (x+1, y+1) (以降「斜め」と表現)

漸化式

 D(n,m) = \begin{cases} 1 &(n=0 \lor m=0) \\ D(n-1, m-1) + D(n-1,m)+D(n,m-1)&(otherwise) \end{cases}

表現方法その1

k を「斜めを使う回数」とする。

k を固定すると，縦 n-k回，横 m-k回，斜め k回を並び替えるので通り数は \binom{n+m-k}{n}\binom{n}{k}。

これをすべての k について足し合わせて

D(n,m) = \displaystyle \sum_{k=0}^{\min(n,m)} \binom{n+m-k}{n}\binom{n}{k}

となる。

表現方法その2

「斜め」のことはおいておいて， n個の「縦」と m個の「横」を並び替えることを考える。

k を「『縦横』と並ぶ回数」とする。

k を固定すると，まず n個の「縦」と m個の「横」を並び替えたときにちょうど k回「縦横」という連続部分列が現れる通り数は \binom{n}{k}\binom{m}{k}となる*1。

また， k個の「縦横」それぞれについてそのまま進むか「斜め」に進むかを選ぶとすると選び方は 2^k 通りある。

これをすべての k について足し合わせて

D(n,m) = \displaystyle \sum_{k=0}^{\min(n,m)} \binom{n}{k}\binom{m}{k}2^k

となる。

この2つ，本当にイコール?

n \leq mとしても一般性を失わない。このとき \min(n,m) = nとなる。

D(n,m) = \displaystyle \sum_{k=0}^{\min(n,m)} \binom{n}{k}\binom{m}{k}2^k

の kを lに置き換えて \min(n,m) = nを適用すると

D(n,m) = \displaystyle \sum_{l=0}^{n} \binom{n}{l}\binom{m}{l}2^l

= \displaystyle \sum_{l=0}^{n} \binom{n}{l}\binom{m}{l} \sum_{k=0}^{l} \binom{l}{k}

= \displaystyle \sum_{l=0}^{n} \sum_{k=0}^{l} \binom{n}{l}\binom{m}{l} \binom{l}{k}

= \displaystyle \sum_{k=0}^{n} \sum_{l=k}^{n} \binom{n}{l}\binom{m}{l} \binom{l}{k}

と書き換えられる*2。あとは

\displaystyle \sum_{l=k}^{n} \binom{n}{l}\binom{m}{l} \binom{l}{k} = \binom{n+m-k}{n}\binom{n}{k}

であることを示せればよい。ここで

\binom{n}{l}\binom{m}{l} \binom{l}{k} = \dfrac{n!m!l!}{l!(n-l)!l!{m-l}!k!(l-k)!}

= \dfrac{n!m!}{(n-l)!l!{m-l}!k!(l-k)!}

= \dfrac{n!(n-k)!m!}{k!(n-k)!l!{m-l}!(n-l)!(l-k)!}

= \dfrac{n!}{k!(n-k)!} \dfrac{(n-k)!}{(n-l)!(l-k)!}\dfrac{m!}{l!{m-l}!}

= \binom{n}{k}\binom{n-k}{n-l} \binom{m}{l}

なので

\displaystyle \sum_{l=k}^{n} \binom{n}{l}\binom{m}{l} \binom{l}{k} = \sum_{l=k}^{n} \binom{n}{k}\binom{n-k}{n-l} \binom{m}{l}

\displaystyle =　\binom{n}{k} \sum_{l=k}^{n} \binom{n-k}{n-l} \binom{m}{l}

となる。最後に

\displaystyle \sum_{l=k}^{n} \binom{n-k}{n-l} \binom{m}{l} = \binom{n+m-k}{n} *3

なので結果的に

\displaystyle \binom{n}{k} \sum_{l=k}^{n} \binom{n-k}{n-l} \binom{m}{l} = \binom{n}{k} \binom{n+m-k}{n}

とかける。よって

\displaystyle \sum_{k=0}^{n} \sum_{l=k}^{n} \binom{n}{l}\binom{m}{l} \binom{l}{k} = \sum_{k=0}^{n} \binom{n}{k} \binom{n+m-k}{n}

で，つまり

\displaystyle \sum_{k=0}^{\min(n,m)} \binom{n+m-k}{n}\binom{n}{k} = \sum_{k=0}^{\min(n,m)} \binom{n}{k}\binom{m}{k}2^k

となる。

なんでこんな記事書いたの?

Wikipedia にあまりにもサラッと書いてあって頭悩ませたのでメモです。

*1:「縦縦...縦」という長さ nの文字列においてそれぞれの文字の後のうち「横」が入る場所を k個選ぶ。同様に「横横...横」という長さ mの文字列においてそれぞれの文字の前のうち「縦」が入る場所を k個選ぶ。例えば (n,m,k)=(4,3,2)の状況で「縦v縦縦v縦」「横v横v横」と選んだとすると生成される文字列は「横縦横縦縦横縦」となる。

*2:これは表現方法その2について「斜め」の個数が同じものをまとめた表現になっている。

*3:ヴァンデルモンドの畳み込みって名前付いてるらしい。