6
自己紹介・記録解説
文献あり

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

534
0

はじめに

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

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

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

本題に入る前に…

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

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

順列の上昇

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

Eulerian number

nを正の整数とする。
Eulerian number nm とは、1,2,,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通りのみ
    なので、
    30=1,31=4,32=1となることがわかる。

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

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

Worpitzky's identity

Worpitzky's identity

任意の正の整数m,nに対して
mn=k=0n1nk(k+mn)
が成り立つ。ただし、ここでは(pq)で二項係数pCqを表しており、p<qのとき(pq)=0と定義する。以下同様に表記する。

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

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

Worpitzky's identityにおいてm=4,n=3の場合

mn=43=64
である。また、例1の結果とあわせて
k=0n1nk(k+mn)=k=023k(k+43)=30(43)+31(53)+32(63)=14+410+120=64
も分かる。よって定理1において()=()=64となり、m=4,n=3の場合に定理1が成り立つことが確かめられた。

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

証明の準備

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

仕切り順列

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

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

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

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

仕切り順列においてm=2,n=3の場合

1,2,3の並びかえで得られる順列のうち、上昇要素がm1=1個以下のものは(132),(213),(231),(312),(321)5つ。これらにm1=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)=mnかつf(m,n)=k=0n1nk(k+mn)
が成り立つことが分かるので、証明終わり、といった感じです。
今あげた2式が成り立つ理由については、自信のある人はぜひ自分で考えてみてください!











それではいよいよ証明です。

方針で定義したようにf(m,n)を定義し、これを2通りで数え上げる。
(1通りめ)
仕切り順列の要素の順番にかかわらず常に仕切りはm1個ある。よって仕切り順列は、m1個の仕切りによってn個の数からなる順列がm個の順列(左から順にp1,p2,,pmとする)に分割されたものと捉えることができる(仕切りが連続する部分については、空集合(のようなもの)として分割されたと考える)。仕切り順列の満たす条件より、各pi(1im)は常に単調減少数列になる(または要素の個数が1あるいは0となる)。したがって、各piに当てはまる要素がすべて決定されるとpiも決定されることになる。ここで、g:{1,2,,n}{1,2,,m}を満たす写像gを考える。任意のx{1,2,,n}についてxpg(x)に当てはめるような割り振り方を考えれば、gと各仕切り順列が一対一に対応することがわかる。各x{1,2,,n}についてg(x)には1,2,,mm通りの値の取り方があるので、gとしてありうるものはmn個ある。したがってf(m,n)=mnを得る。
(2通りめ)
仕切りを加える順列を固定して考える。ここで0kn1を満たすkについて、上昇要素の個数がkであるとする。このときk個の上昇要素の直前に仕切りを入れなければならないので、追加する場所に制限のない仕切りの数はm1kである。m1k<0のときは、ありうる仕切り順列の個数は0であるとしてよく、以下そうでない時を考える。仕切りを入れられる箇所は、順列の要素数がnなのでn+1個あり、仕切りは区別されないので、入れる場所に制限のない仕切りの入れ方は常にひとつにつきn+1通りである。それに加えて、仕切りを入れられる箇所は、そこが左から何番目にあるかによって全て区別される。以上より、入れる場所に制限のない仕切りの入れ方の総数は、n+1個の物の中から重複を許してm1k個の物を選ぶ選び方の総数と等しく、それは((n+1)+(m1k)1m1k)=(n+m1km1k)=(n+m1kn)
に等しい。また、p<qのとき(pq)=0と定義したので、m1kの符号によらず(つまりkの値によらず)、固定された順列に仕切りを加える方法の総数は(n+m1kn)である。一方、上昇要素の個数がkである順列の個数は定義よりnkであるから、以上より上昇要素の個数がkのとき、仕切り順列はnk(n+m1kn)=nn1k(n+m1kn)通り存在する。ここで、nk=nn1kを用いた(順列を右から見ていったときの上昇要素を考えれば証明できる)。よってk0kn1の範囲で動かして、
f(m,n)=k=0n1nn1k(n+m1kn)f(m,n)=k=0n1nk(k+mn)

以上2通りの数え上げにより、
f(m,n)=mn=k=0n1nk(k+mn)
を得るが、これはWorpitzky's identityそのものである。

いかがでしたでしょうか。この方法では、仕切り順列を、仕切りを固定するか順列を固定するかのふた通りで数え上げています。他の方法を思いついた方はぜひ私に教えてください。喜びます。

おわりに

最後まで読んでいただきありがとうございます。幾何でも関数方程式でもなく組み合わせのお話でした。今回は証明の紹介という形になってしまいましたが、次回以降はオリジナルのものについても書けたらいいなと思っています。不備等ありましたらご指摘いただけると嬉しいです。

参考文献

投稿日:2022313
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

翁
48
4044

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 本題に入る前に…
  3. Worpitzky's identity
  4. 証明の準備
  5. 証明
  6. おわりに
  7. 参考文献