はじめに
はじめまして、翁といいます。最初に少し自己紹介を。
- 春から高二
- 競技数学をエンジョイしてます
- その中でも幾何や関数方程式が好き
このくらいかな?
ということで、これだけでは物足りないので、とある恒等式についてのお話をしようと思っています!
ちなみに今回は幾何でも関数方程式でもなくバリバリ違うことに関する話題です、ご注意ください()
本題に入る前に…
その恒等式について考えるために、いくつか言葉や数を定義しておきます。
以下では独自に定義した言葉も含まれています。正式な用語は、定義する際に赤字で書きます。
順列の上昇
順列において、その要素であって (のひとつ前の要素) を満たすようなを順列の上昇要素と呼ぶ。
Eulerian number
を正の整数とする。
Eulerian number とは、の合計個の数の並びかえとして得られる個の順列のうち、その順列の上昇要素がちょうど個存在するようなものすべての総数である。
ちょっと分かりにくいかもしれませんね。の場合を例にとってみましょう。
Eulerian numberにおいての場合
の並びかえとして得られる順列は以下のように通りある:
これらのうち、ひとつ前の要素より大きいような要素がちょうど
- 個ある順列はの通りのみ
- 個ある順列はの通り
- 個ある順列はの通りのみ
なので、
となることがわかる。
一応雰囲気はつかめたでしょうか。それでは、 必要なものを定義し終えたところで早速本題の恒等式に移ってみましょう!
(ちなみに)
Eulerian numberは、日本語では(第一種)オイラリアン数と呼ばれることもあるようですが、ここでは英語のまま表記します。
Worpitzky's identity
Worpitzky's identity
任意の正の整数に対して
が成り立つ。ただし、ここではで二項係数を表しており、のときと定義する。以下同様に表記する。
〜余計なおはなし〜
Worpitzky は人名で、identityは恒等式という意味です(へえ〜)。
Worpitzkyの読み方が分からなかったため英語表記にしました()
それはともかく、二項係数と先程定義したEulerian numberの積の和で累乗が表せてしまうのは驚きですね!これまた分かりにくい形をしているので、具体的にの場合を考えてみます。
Worpitzky's identityにおいての場合
である。また、例1の結果とあわせて
も分かる。よって定理1においてとなり、の場合に定理1が成り立つことが確かめられた。
なるほど、成り立ちそうなことはわかりました。ここまで来たら、なぜ成り立つのかが気になってきますよね?ということで、証明しちゃいましょう!
証明の準備
証明のために、ある条件を満たすように順列に仕切りを追加することを考えます。
仕切り順列
を正の整数とする。の並びかえとして得られる順列のうち、順列の上昇要素の個数が以下であるものに、本の区別されない仕切りを追加する。ただし、追加する際には以下の条件が満たされるようにする。
条件:仕切りを加える前の順列におけるどの上昇要素の直前にも仕切りが追加される
条件が満たされるように仕切りが追加されてできた、仕切りと数の並びのことを、仕切り順列と呼ぶことにする。
なんだか定義というより何かの問題文という感じがしますね。
分かりづらいので例のごとく具体例を見てみましょう。
仕切り順列においての場合
の並びかえで得られる順列のうち、上昇要素が個以下のものはのつ。これらに本の仕切りを追加する。条件より、順列を除く上昇要素の個数がであるつの順列では、仕切りを入れる位置がすべて定まっている。実際に仕切りを加えると、のようになる。また、上昇要素が個である順列においては、仕切りの位置に制限がない。よって、仕切り順列はこのときの通りできる。
以上よりのとき、できる仕切り順列の総数は。
これで証明の準備はおしまいです。それでは証明してみちゃいましょう!
証明
方針
仕切りの個数と順列の要素の個数によって、それらによってできる仕切り順列の総数がただ一通りに定まるので、これをで表すことにしましょう。証明の方針としては、を通りで数え上げることで、かつ
が成り立つことが分かるので、証明終わり、といった感じです。
今あげた式が成り立つ理由については、自信のある人はぜひ自分で考えてみてください!
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
それではいよいよ証明です。
方針で定義したようにを定義し、これを通りで数え上げる。
(通りめ)
仕切り順列の要素の順番にかかわらず常に仕切りは個ある。よって仕切り順列は、個の仕切りによって個の数からなる順列が個の順列(左から順にとする)に分割されたものと捉えることができる(仕切りが連続する部分については、空集合(のようなもの)として分割されたと考える)。仕切り順列の満たす条件より、各は常に単調減少数列になる(または要素の個数があるいはとなる)。したがって、各に当てはまる要素がすべて決定されるとも決定されることになる。ここで、を満たす写像を考える。任意のについてをに当てはめるような割り振り方を考えれば、と各仕切り順列が一対一に対応することがわかる。各についてにはの通りの値の取り方があるので、としてありうるものは個ある。したがってを得る。
(通りめ)
仕切りを加える順列を固定して考える。ここでを満たすについて、上昇要素の個数がであるとする。このとき個の上昇要素の直前に仕切りを入れなければならないので、追加する場所に制限のない仕切りの数はである。のときは、ありうる仕切り順列の個数はであるとしてよく、以下そうでない時を考える。仕切りを入れられる箇所は、順列の要素数がなので個あり、仕切りは区別されないので、入れる場所に制限のない仕切りの入れ方は常にひとつにつき通りである。それに加えて、仕切りを入れられる箇所は、そこが左から何番目にあるかによって全て区別される。以上より、入れる場所に制限のない仕切りの入れ方の総数は、個の物の中から重複を許して個の物を選ぶ選び方の総数と等しく、それは
に等しい。また、のときと定義したので、の符号によらず(つまりの値によらず)、固定された順列に仕切りを加える方法の総数はである。一方、上昇要素の個数がである順列の個数は定義よりであるから、以上より上昇要素の個数がのとき、仕切り順列は通り存在する。ここで、を用いた(順列を右から見ていったときの上昇要素を考えれば証明できる)。よってをの範囲で動かして、
以上通りの数え上げにより、
を得るが、これはWorpitzky's identityそのものである。
いかがでしたでしょうか。この方法では、仕切り順列を、仕切りを固定するか順列を固定するかのふた通りで数え上げています。他の方法を思いついた方はぜひ私に教えてください。喜びます。
おわりに
最後まで読んでいただきありがとうございます。幾何でも関数方程式でもなく組み合わせのお話でした。今回は証明の紹介という形になってしまいましたが、次回以降はオリジナルのものについても書けたらいいなと思っています。不備等ありましたらご指摘いただけると嬉しいです。