4
大学数学基礎解説
文献あり

二項係数の和から母関数へ

1677
0

この記事では数列の母関数を考えることで,鮮やかに計算できる例を紹介します。

二項係数の和を求める

具体的に以下の問題を考えながら話を進めていきます。

二項係数の和

nを正の整数とする。次の和を求めなさい。
⑴ k=0nnCk   ⑵ k=0nknCk   ⑶ k=0nnCkk+1

まずは母関数を使わずに計算してみる

二項定理や組み合わせについて知っていれば,この問題はそれほど難しいものではありません。

⑴ですと二項定理から,
k=0nnCk=(1+1)n=2n
n乗を考えることで計算可能です。

次に⑵についても考えたいですが,次の結果が成り立つことを用いてみます。(証明は簡単ですのでここでは省略します。)

二項係数の性質

n2以上の整数,kを正の整数としたとき,次が成り立つ。knCk=nn1Ck1

よって,n2以上の整数ならば,
k=0nknCk=k=1nknCk=k=1nnn1Ck1=nk=1nn1Ck1=nk=0n1n1Ck=n2n1
と計算できます。途中での番号をずらしたりしていますが,の意味に立ち返れば簡単な式変形です。またn=1のときはk=01k1Ck=1ですので,すべての正の整数nに対してk=0nknCk=n2n1
であることも分かりました。

最後に⑶を考えます。補題 1 の①式より,正の整数n0以上の整数kに対して
(k+1)n+1Ck+1=(n+1)nCk
が成り立ちますので,nCkk+1=n+1Ck+1n+1
です。よって⑵と同様に式変形をしていけば,おのずとk=0nnCkk+1=2n+11n+1
と計算できます。

次に母関数を用いてみる

そもそも数列の母関数ってなんだっけ?という場合がありますので,一応定義しておきます。

有限数列の母関数

有限数列{ak}k=0n母関数 とは,a0+a1x+a2x2++anxn(=k=0nakxk)
というn次関数のことを言う。

母関数を用いて先ほどの問題に別解を与えてみます。

まずは⑴です。数列{nCk}k=0nの母関数が(1+x)nである,というのが二項定理の主張でした。つまり,k=0nnCkxk=(1+x)n(⭐)
です。この⭐式にx=1を代入すればk=0nnCk=2n
と求められます。

⑵,⑶を鮮やかに

次に⑵について考えてみましょう。⑵ではknCkという形の和を求めたいです。というわけで,⭐式の 両辺をxで微分 してみましょう。すると,次の等式を得ます。k=0nnCkkxk1=n(1+x)n1(有限和なのでΣと微分の順序交換を気にしなくていいですね。爽快な気分です。)
ここにx=1を代入することで,k=0nnCkk=n2n1と⑵の結果が鮮やかに求められます!母関数を考えることで微分という演算が可能になり,ここまで綺麗に求められるのです。

では⑶はどうするのだろうというと,積分 を実行してみたいです。特に⭐式の両辺を0から1まで積分してみましょう。すると,01(k=0nnCkxk)dx=01(1+x)ndx
となります。(有限和なのでΣと積分の順序交換を気にせず変形できます。最高。)
それぞれの左辺と右辺を計算することで,k=0nnCkk+1=2n+11n+1
を得ます。これが⑶の答えです。

数列に対して関数を考えることで,微分や積分といった操作が可能になり,より複雑な級数の和を求めることができるようになります。逆に母関数を弄ることで新たな級数の和を発見できるかもしれません。これは母関数を考える1つの利点と言えるでしょう。

利用例:少し面倒な級数

先程の⑵の類似として,次の和を計算してみます。k=0nk2nCk
これを考えるために,やはり⭐式から始めてみましょう。⭐式をxで微分すると,k=0nnCkkxk1=n(1+x)n1
と計算できました。この両辺にxをかけてk=0nnCkkxk=nx(1+x)n1
です。さらにこの両辺をxで微分します。すると,k=0nnCkk2xk1=n(1+x)n1+n(n1)x(1+x)n2
となります。この式にx=1を代入することで,k=0nk2nCk=n2n1+n(n1)2n2=n(n+1)2n2
と計算できました。このように微分してxを掛ける操作を繰り返すことで,複雑(だがキレイ)な和を求めることが出来ます。

利用例:等差×等比

母関数の考えを用いてk=0nk3kを計算してみます。まず次の等式(等比数列の和)を考えます。k=0nxk=xn+11x1
この両辺を微分して,k=0nkxk1=(n+1)xn(x1)(xn+11)(x1)2
この両辺にxをかけ,x=3を代入することで,
k=0nk3k=n(n+1)3n+123n+2+34
と求められます。

おわりに

今回は有限数列のみに話を絞ったため,あまり深い話は出来ませんでしたが,それでも十分面白い話だと思います。

無限数列に対して母関数を考えてあげる話は非常に奥が深く,きれいな理論もあります。例えば以下の参考文献では,母関数への愛が感じられますので,ぜひ閲覧してみてください。(邦訳があるかは存じていません。)

(参考文献のpdfは https://www2.math.upenn.edu/~wilf/DownldGF.html にて閲覧できます。)

参考文献

[1]
Herbert S. Wilf, generatingfunctionology: Third Edition, A K Peters/CRC Press, 2005
投稿日:202119
OptHub AI Competition

この記事を高評価した人

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

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

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

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

投稿者

ぱるち
ぱるち
143
27383
数学屋さんをしています。代数,数論系に興味があり,今は楕円曲線と戯れています。Mathlogは現実逃避用という噂もあります。@f_d00123

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 二項係数の和を求める
  2. まずは母関数を使わずに計算してみる
  3. 次に母関数を用いてみる
  4. 利用例:少し面倒な級数
  5. 利用例:等差×等比
  6. おわりに
  7. 参考文献