二項係数の和の処理(形式的べき級数)
DEGwerさんの数え上げテクニック集の[14.1 頻出公式集]を形式的べき級数などを用いて証明します。
上の参照先にある通り組合せ論的な解釈で片付くものも多いですが、あえて代数的な証明を目指します。
あまりちゃんとした(?)勉強の仕方をしておらず、厳密な正しさに欠けるところも多いと思います。間違っているところや不適切な表現があればご指摘いただけると幸いです。
1~4は割と基本的なので適宜飛ばし読みしてください。
前提知識
ここで、いくつかこの記事で利用する式変形などを確認します。形式的べき級数の定義や基本的な演算についてはこの記事の範囲外とします。
- (記法)
形式的べき級数 を と表した時の の係数をこのように表します。
等比数列の和の公式と思ってもよいと思います。
形式的べき級数 の係数の部分和です。 となることを考えれば自然かと。
- (定義) ( は非負整数)
二項係数です。 とも書かれます。
二項定理。和の取る範囲が普通のものと違っていますが、 のとき なのでよく知られているものと同じといえます。自然数 に対しては、帰納法や組合せの解釈で証明できます。
二項定理のマイナスバージョン。ここらへんの式たちは、テイラー展開の操作も考えてみると面白いかもしれません。
(小ネタ)ここまでで気が付いたかもしれませんが、これらの定理は を任意の複素数に拡張することができます。先ほどのマイナスバージョンも二項定理の を置き換えると出てきます。証明は大変ですが調べてみてください。詳細はWikipedia
ここから実際の内容に入っていきます。
1/6
◇
これは二項定理より明らかです。先ほどの式に を代入するだけですね。
2/6
◇
が奇数の場合が打ち消されてほしいので、上の二項定理の式で を に置換し、下の式を得ます。
これをもとの の式と足し合わせて を代入し で割るとこの等式を得ることができます。
二項係数の漸化式を利用する方法もありますね。そちらの方が簡単かもしれません。
ここまでが普通の関数としての処理になります。
3/6
◇
二項定理のマイナスバージョンを使ってほしそうな顔をしています。
これの係数の部分和をとるだけです。最初の方に挙げた公式を使います。
ここでついさっき使ったばかりの二項定理をもう一度逆に使うと、欲しい式が現れます。
行って帰ってきたらちょっと違う顔をしてた、みたいな感じでおもしろい。
一応この等式はパスカルの三角形での和を考えると直感的です。
4/6
◇
(出典と少し違いますが、こちらの式が正しいはずです)
先ほどのものとほとんど同じですね。3/6の式をシグマの数だけ適用します。もサラっと2回使っています。
たどり着けました。
先ほど同様、パスカルの三角形で長方形の部分の和をとると言い換えられ、3.の手順を2重に繰り返せばイメージが付きます。
ここまでは単に公式を当てはめることで和の計算ができ、イメージも容易でした。
次から式が複雑になり、解釈が難しくなってきます。
5/6
◇
二項係数同士の積が出てきました。一筋縄ではいかなそうに見えます。
このような形の式はしばしば、以下のようなで手順で計算できるようです。
- シグマの中身を変数をひとつ選んで(ここでは とする) と表す。ここは経験(と試行錯誤)が必要?
- を係数に持つ形式的べき級数 をおく。
- シグマの順序を入れ換え、式をくくりだすなどして簡単な形にもっていく。
- の形にバラす。
この通りにやってみます。
- 選ぶ変数として が考えられます。ここでは の動く範囲が中途半端で扱いづらいので にします。
- とおきます。
- より
できました!
これはVandermondeの恒等式と呼ばれるものらしいです。最終的にはの係数を比較しているだけだということもわかりました。
6/6
◇
同じです。
- を選びます。
- とおきます。
- より
個人的にはこのやり方はずっと頭を使わずに済みます。もちろんいつもうまくいく訳では決してありませんが。
5つ目と比べて新しいものが少なくてちょっと残念です。
おわりに
ここではとても限られたことしか紹介しませんでしたが、形式的べき級数や二項係数の世界はずっと奥深く、自分もまだまだ勉強中です。
形式的べき級数について参考になる/おもしろい記事のリンクをいくつか貼っておきます。主な対象や読みやすさはかなりバラバラです。
[多項式・形式的べき級数](1)数え上げとの対応付け | maspyのHP
[数学] 形式的べき級数による数え上げ(AtCoder JSC2019予選問題F) | maspyのHP
IMOmath: Theory of Generating Functions
http://yufeizhao.com/olympiad/comb3.pdf#page=3
今年中に理解する!多項式、母関数、形式的べき級数の競プロでの実践的使い方 - はまやんはまやんはまやん
https://www.math.ust.hk/excalibur/v13_n5.pdf
(二項係数)http://izumi-math.jp/I_Yanagita/binomial_theorem_proof.pdf
WolframAlphaはすごい。