自己紹介&Worpitzky's identityについてのお話

自己紹介

551

はじめに

はじめまして、翁といいます。最初に少し自己紹介を。

春から高二
競技数学をエンジョイしてます
その中でも幾何や関数方程式が好き

このくらいかな？
ということで、これだけでは物足りないので、とある恒等式についてのお話をしようと思っています！
ちなみに今回は幾何でも関数方程式でもなくバリバリ違うことに関する話題です、ご注意ください()

本題に入る前に…

その恒等式について考えるために、いくつか言葉や数を定義しておきます。

以下では独自に定義した言葉も含まれています。正式な用語は、定義する際に赤字で書きます。

順列の上昇

順列 $p$ において、その要素 $x$ であって ( $x$ のひとつ前の要素) $< x$ を満たすような $x$ を順列 $p$ の上昇要素と呼ぶ。

Eulerian number

$n$ を正の整数とする。
Eulerian number $⟨ \binom{n}{m} ⟩$ とは、 $1, 2, \dots, n$ の合計 $n$ 個の数の並びかえとして得られる $n!$ 個の順列のうち、その順列の上昇要素がちょうど $m$ 個存在するようなものすべての総数である。

ちょっと分かりにくいかもしれませんね。 $n = 3$ の場合を例にとってみましょう。

Eulerian numberにおいて

n = 3

の場合

$1, 2, 3$ の並びかえとして得られる順列は以下のように $3! = 6$ 通りある:
$(123), (132), (213), (231), (312), (321)$
これらのうち、ひとつ前の要素より大きいような要素がちょうど

$0$ 個ある順列は $(321)$ の $1$ 通りのみ
$1$ 個ある順列は $(132), (213), (231), (312)$ の $4$ 通り
$2$ 個ある順列は $(123)$ の $1$ 通りのみ
なので、
$⟨ \binom{3}{0} ⟩ = 1, ⟨ \binom{3}{1} ⟩ = 4, ⟨ \binom{3}{2} ⟩ = 1$ となることがわかる。

一応雰囲気はつかめたでしょうか。それでは、必要なものを定義し終えたところで早速本題の恒等式に移ってみましょう！

(ちなみに)
Eulerian numberは、日本語では(第一種)オイラリアン数と呼ばれることもあるようですが、ここでは英語のまま表記します。

Worpitzky's identity

任意の正の整数 $m, n$ に対して
$m^{n} = \sum_{k = 0}^{n - 1} ⟨ \binom{n}{k} ⟩ (\begin{matrix} k + m \\ n \end{matrix})$
が成り立つ。ただし、ここでは $(\begin{matrix} p \\ q \end{matrix})$ で二項係数 $_{p} C_{q}$ を表しており、 $p < q$ のとき $(\begin{matrix} p \\ q \end{matrix}) = 0$ と定義する。以下同様に表記する。

〜余計なおはなし〜
Worpitzky は人名で、identityは恒等式という意味です(へえ〜)。
Worpitzkyの読み方が分からなかったため英語表記にしました()

それはともかく、二項係数と先程定義したEulerian numberの積の和で累乗が表せてしまうのは驚きですね！これまた分かりにくい形をしているので、具体的に $m = 4, n = 3$ の場合を考えてみます。

Worpitzky's identityにおいて

m = 4, n = 3

の場合

$m^{n} = 4^{3} = 64$
である。また、例1の結果とあわせて
$\begin{aligned} \sum_{k = 0}^{n - 1} ⟨ \binom{n}{k} ⟩ (\begin{array}{c} k + m \\ n \end{array}) & = \sum_{k = 0}^{2} ⟨ \binom{3}{k} ⟩ (\begin{array}{c} k + 4 \\ 3 \end{array}) \\ = ⟨ \binom{3}{0} ⟩ (\begin{array}{c} 4 \\ 3 \end{array}) + ⟨ \binom{3}{1} ⟩ (\begin{array}{c} 5 \\ 3 \end{array}) + ⟨ \binom{3}{2} ⟩ (\begin{array}{c} 6 \\ 3 \end{array}) \\ = 1 \cdot 4 + 4 \cdot 10 + 1 \cdot 20 \\ = 64 \end{aligned}$
も分かる。よって定理1において $(左辺) = (右辺) = 64$ となり、 $m = 4, n = 3$ の場合に定理1が成り立つことが確かめられた。

なるほど、成り立ちそうなことはわかりました。ここまで来たら、なぜ成り立つのかが気になってきますよね？ということで、証明しちゃいましょう！

証明の準備

証明のために、ある条件を満たすように順列に仕切りを追加することを考えます。

仕切り順列

$m, n$ を正の整数とする。 $1, 2, \dots, n$ の並びかえとして得られる順列のうち、順列の上昇要素の個数が $m - 1$ 以下であるものに、 $m - 1$ 本の区別されない仕切りを追加する。ただし、追加する際には以下の条件が満たされるようにする。

条件:仕切りを加える前の順列におけるどの上昇要素の直前にも仕切りが追加される

条件が満たされるように仕切りが追加されてできた、仕切りと数の並びのことを、仕切り順列と呼ぶことにする。

なんだか定義というより何かの問題文という感じがしますね。
分かりづらいので例のごとく具体例を見てみましょう。

仕切り順列において

m = 2, n = 3

の場合

$1, 2, 3$ の並びかえで得られる順列のうち、上昇要素が $m - 1 = 1$ 個以下のものは $(132), (213), (231), (312), (321)$ の $5$ つ。これらに $m - 1 = 1$ 本の仕切りを追加する。条件より、順列 $(321)$ を除く上昇要素の個数が $1$ である $4$ つの順列では、仕切りを入れる位置がすべて定まっている。実際に仕切りを加えると、 $(1 | 32), (21 | 3), (2 | 31), (31 | 2)$ のようになる。また、上昇要素が $0$ 個である順列 $(321)$ においては、仕切りの位置に制限がない。よって、仕切り順列はこのとき $(| 321), (3 | 21), (32 | 1), (321 |)$ の $4$ 通りできる。
以上より $m = 1, n = 3$ のとき、できる仕切り順列の総数は $8$ 。

これで証明の準備はおしまいです。それでは証明してみちゃいましょう！

証明

方針

仕切りの個数 $m$ と順列の要素の個数 $n$ によって、それらによってできる仕切り順列の総数がただ一通りに定まるので、これを $f (m, n)$ で表すことにしましょう。証明の方針としては、 $f (m, n)$ を $2$ 通りで数え上げることで、 $f (m, n) = m^{n}$ かつ $f (m, n) = \sum_{k = 0}^{n - 1} ⟨ \binom{n}{k} ⟩ (\begin{matrix} k + m \\ n \end{matrix})$
が成り立つことが分かるので、証明終わり、といった感じです。
今あげた $2$ 式が成り立つ理由については、自信のある人はぜひ自分で考えてみてください！
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
それではいよいよ証明です。

方針で定義したように $f (m, n)$ を定義し、これを $2$ 通りで数え上げる。
( $1$ 通りめ)
仕切り順列の要素の順番にかかわらず常に仕切りは $m - 1$ 個ある。よって仕切り順列は、 $m - 1$ 個の仕切りによって $n$ 個の数からなる順列が $m$ 個の順列(左から順に $p_{1}, p_{2}, \dots, p_{m}$ とする)に分割されたものと捉えることができる(仕切りが連続する部分については、空集合(のようなもの)として分割されたと考える)。仕切り順列の満たす条件より、各 $p_{i} (1 \leq i \leq m)$ は常に単調減少数列になる(または要素の個数が $1$ あるいは $0$ となる)。したがって、各 $p_{i}$ に当てはまる要素がすべて決定されると $p_{i}$ も決定されることになる。ここで、 $g : {1, 2, \dots, n} \to {1, 2, \dots, m}$ を満たす写像 $g$ を考える。任意の $x \in {1, 2, \dots, n}$ について $x$ を $p_{g (x)}$ に当てはめるような割り振り方を考えれば、 $g$ と各仕切り順列が一対一に対応することがわかる。各 $x \in {1, 2, \dots, n}$ について $g (x)$ には $1, 2, \dots, m$ の $m$ 通りの値の取り方があるので、 $g$ としてありうるものは $m^{n}$ 個ある。したがって $f (m, n) = m^{n}$ を得る。
( $2$ 通りめ)
仕切りを加える順列を固定して考える。ここで $0 \leq k \leq n - 1$ を満たす $k$ について、上昇要素の個数が $k$ であるとする。このとき $k$ 個の上昇要素の直前に仕切りを入れなければならないので、追加する場所に制限のない仕切りの数は $m - 1 - k$ である。 $m - 1 - k < 0$ のときは、ありうる仕切り順列の個数は $0$ であるとしてよく、以下そうでない時を考える。仕切りを入れられる箇所は、順列の要素数が $n$ なので $n + 1$ 個あり、仕切りは区別されないので、入れる場所に制限のない仕切りの入れ方は常にひとつにつき $n + 1$ 通りである。それに加えて、仕切りを入れられる箇所は、そこが左から何番目にあるかによって全て区別される。以上より、入れる場所に制限のない仕切りの入れ方の総数は、 $n + 1$ 個の物の中から重複を許して $m - 1 - k$ 個の物を選ぶ選び方の総数と等しく、それは $(\begin{matrix} (n + 1) + (m - 1 - k) - 1 \\ m - 1 - k \end{matrix}) = (\begin{matrix} n + m - 1 - k \\ m - 1 - k \end{matrix}) = (\begin{matrix} n + m - 1 - k \\ n \end{matrix})$
に等しい。また、 $p < q$ のとき $(\begin{matrix} p \\ q \end{matrix}) = 0$ と定義したので、 $m - 1 - k$ の符号によらず(つまり $k$ の値によらず)、固定された順列に仕切りを加える方法の総数は $(\begin{matrix} n + m - 1 - k \\ n \end{matrix})$ である。一方、上昇要素の個数が $k$ である順列の個数は定義より $⟨ \binom{n}{k} ⟩$ であるから、以上より上昇要素の個数が $k$ のとき、仕切り順列は $⟨ \binom{n}{k} ⟩ (\begin{matrix} n + m - 1 - k \\ n \end{matrix}) = ⟨ \binom{n}{n - 1 - k} ⟩ (\begin{matrix} n + m - 1 - k \\ n \end{matrix})$ 通り存在する。ここで、 $⟨ \binom{n}{k} ⟩ = ⟨ \binom{n}{n - 1 - k} ⟩$ を用いた(順列を右から見ていったときの上昇要素を考えれば証明できる)。よって $k$ を $0 \leq k \leq n - 1$ の範囲で動かして、
$\begin{aligned} f (m, n) & = \sum_{k = 0}^{n - 1} ⟨ \binom{n}{n - 1 - k} ⟩ (\begin{array}{c} n + m - 1 - k \\ n \end{array}) \\ f (m, n) & = \sum_{k = 0}^{n - 1} ⟨ \binom{n}{k} ⟩ (\begin{array}{c} k + m \\ n \end{array}) \end{aligned}$

以上 $2$ 通りの数え上げにより、
$f (m, n) = m^{n} = \sum_{k = 0}^{n - 1} ⟨ \binom{n}{k} ⟩ (\begin{matrix} k + m \\ n \end{matrix})$
を得るが、これはWorpitzky's identityそのものである。