初めに
二項係数に関する恒等式の組合せ的な解き方を紹介します。
、包除原理
包除原理の解説
、主客転倒を主に使っていきます!
有名な恒等式でも、僕が組合せ的に解くことができなかったり、組合せ的に解けても汚かったり、結局母関数の問題に帰着される方法しか分からなかったものは省いています...
実用性があるかはかなり分かれると思っています。
ただエレガントさ、面白さは絶対にほかの証明方には負けません!
間違いがあると教えてほしいです。
またの時とします。
Level1
1,
個の区別するボールを個選択する組合せについて考える。これは通りである。
別の数え方をしてみる
一つのボールに着目してそのボールを選択するとき:残りの個から個選択すればいいので通り
そのボールを選択しない時:残りの個から個選択すればいいので、通り
よって
2,(は自然数)
二項定理より一瞬で示すことができる。
個の区別するボールを非負整数個選択し選択したボールを個の箱に分配する(空の箱があってもよい)組合せについて考える。
選択するボールが個の時、通り。よって求めたい組合せはが0の時からの時まで足し合わせると求められるので、通り
別の数えかたをしてみる。
箱を新たに一つ追加してそれを箱と呼ぶことにする。
選択しないボールを箱に入れると言い換えることで、求めたい組合せは通りとなる。
mが自然数の時にしか示せないので面白さ以外完全に下位互換である。
3,
区別する個のボールを偶数個選択する組合せについて考える
選択するボールが個であるとき、組合せは通り。そしてがの時からのときまで足し合わせると求められるので、求めたい組合せは通り
別の数え方をしてみる。
個のボールのうち一つボールを決めそれをボールとする。
ボール以外の個のボールについて考え、そのボールを非負整数個選択する。この組み合わせは通りである。この時、選択したボールが偶数個であるなら、ボールを選択せず、選択したボールが奇数個であるときはボールを選択することで、求めたい組合せを得ることができる。よって通り。
4,
個の区別する白いボールがあり、そのうち個を赤色に塗り、 つを青色に塗る組合せについて考える。
個のボールの中から染色するボールを個選び、選んだ個の中から一つ青色に塗るボールを決め、残りの個を赤色に塗ると良いので、求めたい組合せは通り。
別の数え方をしてみる。
先に青色に塗るボールを個の中から選び、残りの個のボールの中から赤色に塗るボールを選ぶと良いので、求めたい組合せは通り
Level2
5,
2,4より一瞬で分かる
個の区別する箱があり、すべての箱の中に個の区別できる玉が入っている。
このとき非負整数個の箱を選び、選んだ箱から一つずつボールを選択する組合せは、すべての箱について
{個のうちどの玉を選択するか(通り)} or {その箱を選ばない(ボールをとらない)}選択を回することになるので、通り。
ここで以下のようなことを考えてみる。
玉の取り出し方通りすべてについて選択された玉の数の合計はいくつか?
選択する箱が個の時で場合分けをしてそれを足し合わせることで求めてみる。
選択する箱が個の時
箱の選択の仕方は通り。
玉の選択の仕方は通り。
よって、選択された玉の数の合計はとなる。
したがって求めたい「玉の取り出し方通りすべてについて選択された玉の数の合計」は
となる。
別の方法で求めてみる。
ここで競技数学でよく使われる主客転倒という手法を使います。
玉はすべてで個あります。このうち一つの玉に着目してそれを玉とします。
この時、玉が何回カウントされるか数え、それにを掛けることで、「玉の取り出し方通りすべてについて選択された玉の数の合計」求めることができる。
玉が選択された時、残りの個の箱すべてについて、個のうちどの玉を選択するか(通り) or その箱を選ばない(ボールをとらない)選択をすることになる。したがって玉が選択される組合せは通りとなる。これは玉が選択された玉の合計として回足されることを意味する。
したがって「玉の取り出し方通りすべてについて選択された玉の数の合計」はとなる。
6, 恒等式
個の|と個の○を並び変える組合せについて考える。
この並べ替えは 通りである。
別の方法で数えてみる。
一番右側にある|に着目してそれより右側にある○の数で場合分けをして、それを足し合わせることで求めてみる。
一番右側にある|の右に○が個あるとき、それより左にある|個と○個を自由に並びかえたらいいので、通りとなる。
したがって求めたい組合せは通りとなる。
パスカルの三角形を使った証明もかなりエレガントだと思っています。
7,の畳み込み
神恒等式です これに関しては組合せ的証明のほうがシンプルで分かりやすいと思ってます!
箱に個、箱に個の区別できるボールが入っています。
この中から合計個ボールを選択する組合せについて考える。
箱,からいくつのボールを選択するか場合分けをして、それを足し合わせることで求めてみる。
箱から個、箱から個選択する時、通りとなる。
したがって求めたい組合せは
通りとなる。
別の方法で求めてみる
箱を無視して、全部で個ボールがある中から個のボールを選択すればいいので、
求めたい組合せは通りとなる。
Level3
8,
個の星があります。
ここで直行便というものを以下のように定義します。
直行便:始点として設定された一つの星から、終点として設定された一つの星を結ぶ一方通行の便。但し、始点と終点を同じ星にすることができる。
この時、以下の条件を満たす直行便の組合せについて数える。
条件:直行便の数は個であり、すべての星は最低一つの始点と終点に設定されている。
この条件を満たす直行便の組合せは、個の星の並び替えに等しいので通り
別の数え方をしてみる。
条件を以下のように少し変える。
条件:直行便の数は個であり、すべての星は最低一つの始点に設定されているが必ずしも終点に設定されてるとは限らない。
この条件を満たす直行便の組合せは、すべての直行便について個ある星の中から終点を選ぶ。この選択を回するので、通りである。
この中から最初に設定した「すべての星は最低一つの終点に設定されている」という条件を満たさないものを引くことで最初の条件を満たす直行便の組合せを求める。
ここで包除原理を使います。星を()とし、
(星が終点として設定されてない組合せ)(星と星が終点として設定されてない組合せ)
(星と星と星が終点として設定されてない組合せ)...
上記のようにして求めることができる。
したがって、求めたい組合せは、=
9,
段の階段を考える。
君はその階段を一歩で段または段進むことができます。但し、君は通りの方法で一歩で段進むことができます。(これからは一歩で段進むことを「1段飛ばし」、一歩で段進むことを「普通」と呼ぶことにする。)
この時、君が段の階段を昇る方法は何通りあるか考える。
一段飛ばしを何回するかで場合分けをしてそれを足し合わせることで求めてみる。
一段飛ばしを回するとき、君は普通と一段飛ばしを合計回することになるので、一段飛ばしと普通の並び替えは通り。
一段飛ばしは種類あるので、一段飛ばしを回行うとき通りとなる。
別の数え方をしてみる。
求めたい組合せをとおき漸化式を立てる。
段の昇り方は段昇ったあと一段進む又は、段昇った後一段飛ばしをすることによって得られるので、
という漸化式が得られる。
この漸化式を解くとが得られる。
最後に
8の説明がかなり大変でした...包除原理を説明すること自体かなり難しい...
まだ紹介したいものがありますが、これくらいにしておきます...