場合の数を恒等式に利用できるか

場合の数や確率の問題を解く際、
「もっと簡単に求める方法があったか！」と感じることがあると思う。

ちょっとしたことに気づくだけで、立式はいたって単純になるはずだったのに、
それに気づかなかったせいで無駄に多くの計算をしてしまう。場合の数や確率の計算時に多く見られることだ。
もちろん、それも丹念に計算をしていけば、確かに正解にたどり着くだろう。

このことにちょっと注目してみたい。
というのも、ある日ふと思ったのだ。
「…これで恒等式ができはしないか?」



具体的に、こんな例がある↓
【問題】ｎ個の区別できる球を、箱Ａか箱Ｂにそれぞれ入れる入れ方は何通りか？

【解答１】
１つ１つの球に注目して、それぞれが箱Ａに入るか箱Ｂに入るかの問題はそれぞれの球ごとで
独立しているので入れ方の総数は　２ⁿ　通り

【解答２】
Ａに入る球の数aに注目して場合分けする
a＝０のとき　全ての球がＢに入るから入れる方法は　１通り
a＝１のとき　n個の球のうち１つが箱Ａに入るのだから入れる方法は　nC1　通り
a＝２,３,４…nの場合も同様に考えるとそれぞれ
nC2,nC3,nC4,…nCn 　である
よって入れ方の総数は　nC0 +　nC1 + nC2 + nC3 +...+ nCn　通り


この２つの解答、もちろん同じものを求めているわけだから
この問題を通して
 n
 Σ nCk ＝　２ⁿ　 　が得られたことになる。
k=0


このように、
場合の数や確率論から、新たな恒等式を得られる可能性、また、
すでに知られている恒等式が、組み合わせや確率の観点を使うことで覚えやすくなる可能性
が望めるわけだ。これは耳よりではないか。

好きなように問題を想定してみてどんな恒等式ができるか考えてみるのも面白いし、
ちょっと覚えにくい恒等式を、場合の数や確率の観点で導き出せないか考えて、思いつくことができたら便利だと思う。



簡単な例を一つ見つけた。（また場合の数から導く例になってしまうけれど…）
★　aⁿ - bⁿ = (a-b)( a^n-1 + a^n-2b + a^n-3b² + … + ab^n-2 + b^n-1 )

整数問題なんかでよく使うことがある、身近な恒等式。
左辺の－に注目してこんな状況を思いつける。

男子b人、女子a-b人、計a人で構成されるクラスがnクラスある。
各クラスから一人ずつ選出してn人で構成されたグループを１つ作るとき、
少なくとも女子が一人いるようなグループの作り方は何通りか。


男女を考慮しないグループの作り方がaⁿ通りで、
男子のみで構成されるグループの作り方がbⁿ通りだから、作り方の総数はaⁿ - bⁿ 通り
これで答えが aⁿ - bⁿ になる問題が作れた。


では右辺を導くための考え方を探る。
各クラスを１組，２組，３組，・・・ｎ組　と呼ぶことにして、
「女子が選出されたクラスのうち一番数字が若いクラス」によって場合分けするとうまくいきそうだ。

◆１組で女子が選出される場合◆
　１組からの女子の選出の仕方がa-b通り、
　２組以降のn-1クラスでは男女問わない（すでに女子が選ばれているから）ので各a通り
　よって　　　　　　(a-b)a^n-1　通り

◆１組では男子、２組では女子が選出される場合◆
　１組からの男子の選出の仕方がb通り、
　２組からの女子の選出の仕方がa-b通り
　３組以降のn-2クラスは男女問わないので各a通り
　よって　　　　b*(a-b)*a^n-2　通り

◆２組までのクラスでは男子、３組では女子が選出される場合◆
　２組までの２クラスからの男子の選出の仕方が各b通り、
　３組からの女子の選出の仕方がa-b通り
　４組以降のn-3クラスは男女問わないので各a通り）
　よって　　　b²*(a-b)*a^n-3　通り
・
・
・
◆n-1組までのクラスでは男子、n組では女子が選出される場合◆
　n-1組までのn-1からの男子の選出の仕方が各b通り、
　n組からの女子の選出の仕方がa-b通り
　よって　　　　　b^n-1*(a-b)　通り

以上により求める組み合わせの数は
(a-b)a^n-1 + (a-b)a^n-2b + (a-b)a^n-3b² + … + (a-b)ab^n-2 + (a-b)b^n-1となり、
(a-b)でくくって
(a-b)( a^n-1 + a^n-2b + a^n-3b² + … + ab^n-2 + b^n-1 )　　（＝★の右辺）　が導かれた。



ただこうして導かれた等式ではaとbが自然数という条件つきなのは難点かも?
――まあこの場合は任意の実数mでも使って、両辺にmⁿをかけてやれば
am =k , bm =ℓ とおいて
kⁿ - ℓⁿ = (k-ℓ)( k^n-1 + k^n-2ℓ + k^n-3ℓ² + … + kℓ^n-2 + ℓ^n-1 )
が成立するから、適用が実数の範囲まで広げられることになると思うけれど――


今回はすごくシンプルな例だったけれど(わざわざ場合の数で考える必要もないようなorz)、
これをステップに、もっと面白いものが生まれることを期待して、今後恒等式を見たり、場合の数や確率の問題を解いたりするたびにちょっとでも考えてみたい。
思いつき次第また記事にしようと思う。