12
高校数学解説
文献あり

二項係数に関する恒等式の組合せ的な証明

921
0

初めに

二項係数に関する恒等式の組合せ的な解き方を紹介します。
doublecounting、包除原理 包除原理の解説 、主客転倒を主に使っていきます!
有名な恒等式でも、僕が組合せ的に解くことができなかったり、組合せ的に解けても汚かったり、結局母関数の問題に帰着される方法しか分からなかったものは省いています...
実用性があるかはかなり分かれると思っています。
ただエレガントさ、面白さは絶対にほかの証明方には負けません!
間違いがあると教えてほしいです。
またr<0,n<rの時nCr=0とします。

Level1

1,nCr=n1Cr1+n1Cr

n個の区別するボールをr個選択する組合せについて考える。これはnCr通りである。
別の数え方をしてみる
一つのボールに着目してそのボールを選択するとき:残りのn1個からr1個選択すればいいのでn1Cr1通り
そのボールを選択しない時:残りのn1個からr個選択すればいいので、n1Cr通り
よってnCr=n1Cr1+n1Cr

2,k=0nmknCk=(m+1)n(mは自然数)

二項定理より一瞬で示すことができる。
n個の区別するボールを非負整数個選択し選択したボールをm個の箱に分配する(空の箱があってもよい)組合せについて考える。
選択するボールがk個の時、mknCk通り。よって求めたい組合せはkが0の時からnの時まで足し合わせると求められるので、k=0nmknCk通り
別の数えかたをしてみる。
箱を新たに一つ追加してそれを箱Xと呼ぶことにする。
選択しないボールを箱Xに入れると言い換えることで、求めたい組合せは(m+1)n通りとなる。
mが自然数の時にしか示せないので面白さ以外完全に下位互換である。

3,k=0n2nC2k=2n1

区別するn個のボールを偶数個選択する組合せについて考える
選択するボールが2k個であるとき、組合せはnC2k通り。そしてk0の時からn2のときまで足し合わせると求められるので、求めたい組合せはk=0n2nC2k通り
別の数え方をしてみる。
n個のボールのうち一つボールを決めそれをボールXとする。
ボールX以外のn1個のボールについて考え、そのボールを非負整数個選択する。この組み合わせは2n1通りである。この時、選択したボールが偶数個であるなら、ボールXを選択せず、選択したボールが奇数個であるときはボールXを選択することで、求めたい組合せを得ることができる。よって2n1通り。

4,rnCr=nn1Cr1

n個の区別する白いボールがあり、そのうちr1個を赤色に塗り、1 つを青色に塗る組合せについて考える。
n個のボールの中から染色するボールをr個選び、選んだr個の中から一つ青色に塗るボールを決め、残りのr1個を赤色に塗ると良いので、求めたい組合せはrnCr通り。
別の数え方をしてみる。
先に青色に塗るボールをn個の中から選び、残りのn1個のボールの中から赤色に塗るボールを選ぶと良いので、求めたい組合せはnn1Cr1通り

Level2

5,k=0nmkknCk=mn(m+1)n1

2,4より一瞬で分かる
n個の区別する箱があり、すべての箱の中にm個の区別できる玉が入っている。
このとき非負整数個の箱を選び、選んだ箱から一つずつボールを選択する組合せは、すべての箱について
{m個のうちどの玉を選択するか(m通り)} or {その箱を選ばない(ボールをとらない)}選択をn回することになるので、(m+1)n通り。
ここで以下のようなことを考えてみる。

玉の取り出し方(m+1)n通りすべてについて選択された玉の数の合計はいくつか?

選択する箱がk個の時で場合分けをしてそれを足し合わせることで求めてみる。
選択する箱がk個の時
箱の選択の仕方はnCk通り。
玉の選択の仕方はmk通り。
よって、選択された玉の数の合計はmkknCkとなる。
したがって求めたい「玉の取り出し方(m+1)n通りすべてについて選択された玉の数の合計」は
k=0nmkknCkとなる。

別の方法で求めてみる。

ここで競技数学でよく使われる主客転倒という手法を使います。
玉はすべてでmn個あります。このうち一つの玉に着目してそれを玉Xとします。
この時、玉Xが何回カウントされるか数え、それにmnを掛けることで、「玉の取り出し方(m+1)n通りすべてについて選択された玉の数の合計」求めることができる。

Xが選択された時、残りのn1個の箱すべてについて、m個のうちどの玉を選択するか(m通り) or その箱を選ばない(ボールをとらない)選択をすることになる。したがって玉Xが選択される組合せは(m+1)n1通りとなる。これは玉Xが選択された玉の合計として(m+1)n1回足されることを意味する。

したがって「玉の取り出し方(m+1)n通りすべてについて選択された玉の数の合計」はmn(m+1)n1となる。

6,k=0mn+kCk=n+m+1Cm hockeystick恒等式

n+1個の|とm個の○を並び変える組合せについて考える。
この並べ替えはn+m+1Cm 通りである。

別の方法で数えてみる。

一番右側にある|に着目してそれより右側にある○の数で場合分けをして、それを足し合わせることで求めてみる。
一番右側にある|の右に○がnk個あるとき、それより左にある|n個と○k個を自由に並びかえたらいいので、n+kCk通りとなる。
したがって求めたい組合せはk=0mn+kCk通りとなる。

パスカルの三角形を使った証明もかなりエレガントだと思っています。

7,k=0rnCk×mCrk=n+mCrvandermondeの畳み込み

神恒等式です これに関しては組合せ的証明のほうがシンプルで分かりやすいと思ってます!

An個、箱Bm個の区別できるボールが入っています。
この中から合計r個ボールを選択する組合せについて考える。
A,Bからいくつのボールを選択するか場合分けをして、それを足し合わせることで求めてみる。
Aからk個、箱Bからrk個選択する時、nCk×mCrk通りとなる。
したがって求めたい組合せは
k=0rnCk×mCrk通りとなる。

別の方法で求めてみる

箱を無視して、全部でn+m個ボールがある中からr個のボールを選択すればいいので、
求めたい組合せはn+mCr通りとなる。

Level3

8,k=0n(1)k+nknnCk=n!

n個の星があります。
ここで直行便というものを以下のように定義します。
直行便:始点として設定された一つの星から、終点として設定された一つの星を結ぶ一方通行の便。但し、始点と終点を同じ星にすることができる。

この時、以下の条件を満たす直行便の組合せについて数える。
条件:直行便の数はn個であり、すべての星は最低一つの始点と終点に設定されている。

この条件を満たす直行便の組合せは、n個の星の並び替えに等しいのでn!通り

別の数え方をしてみる。

条件を以下のように少し変える。
条件:直行便の数はn個であり、すべての星は最低一つの始点に設定されているが必ずしも終点に設定されてるとは限らない。

この条件を満たす直行便の組合せは、すべての直行便についてn個ある星の中から終点を選ぶ。この選択をn回するので、nn通りである。

この中から最初に設定した「すべての星は最低一つの終点に設定されている」という条件を満たさないものを引くことで最初の条件を満たす直行便の組合せを求める。

ここで包除原理を使います。星を(H1,H2,H3,...,Hn)とし、

(星Hkが終点として設定されてない組合せ)(星Hkと星Hlが終点として設定されてない組合せ)
+(星Hkと星Hlと星Hmが終点として設定されてない組合せ)...

上記のようにして求めることができる。
したがって、求めたい組合せは、nnk=1n(1)k+1(nk)nnCk=k=0n(1)k+nknnCk

9,k=0n2mknkCk=14m+1{(1+4m+12)n+1(14m+12)n+1}

n段の階段を考える。
A君はその階段を一歩で1段または2段進むことができます。但し、A君はm通りの方法で一歩で2段進むことができます。(これからは一歩で2段進むことを「1段飛ばし」、一歩で1段進むことを「普通」と呼ぶことにする。)
この時、A君がn段の階段を昇る方法は何通りあるか考える。

一段飛ばしを何回するかで場合分けをしてそれを足し合わせることで求めてみる。
一段飛ばしをk回するとき、A君は普通と一段飛ばしを合計nk回することになるので、一段飛ばしと普通の並び替えはnkCk通り。
一段飛ばしはm種類あるので、一段飛ばしをk回行うときmknkCk通りとなる。

別の数え方をしてみる。

求めたい組合せをanとおき漸化式を立てる。a1=1,a2=m+1
n+2段の昇り方はn+1段昇ったあと一段進む又は、n段昇った後一段飛ばしをすることによって得られるので、
an+2=an+1+manという漸化式が得られる。
この漸化式を解くとan=14m+1{(1+4m+12)n+1(14m+12)n+1}が得られる。

最後に

8の説明がかなり大変でした...包除原理を説明すること自体かなり難しい...
まだ紹介したいものがありますが、これくらいにしておきます...

参考文献

投稿日:22
OptHub AI Competition

この記事を高評価した人

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

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

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

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

投稿者

OMC水 ScienceTokyo工学院志望

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中