【高校数学のツボ】 組合せの数に関する漸化式。

とある大学の入試問題に次のような問題があった。


＜問題＞

n 枚のカードがあり，それぞれに1からnまでの数字のうちのどれかが一つだけ書かれている。このカードから k 枚取り出したとき，書かれている数字の最大値が r であるような場合の数を求めよ。


この問題に対するアプローチは二通り考えられる。

以下では，a 個の異なるものから b 個取り出す組合せの数を (a,b) と表すことにする。


＜＜アプローチその1＞＞

数字 r を一枚先に取り出し，それを k 枚のうちの1枚として確保しておくことにする。残りの k-1 枚のカードは，1～ (r-1) の数字が書かれたカードから選ぶことにすれば取り出し方に関する条件を満たす。したがって，求める場合の数は (r-1,k-1) である。

＜＜アプローチその2＞＞

書かれている数字が r 以下であるのは，1～r までのカードから k 枚取り出した場合であり，(r,k) 通りある。

この中にはカードの数字の最大値が r-1 以下のものが含まれているから，そのような場合 (r-1,k) 通りを除けば，最大の数字が r であるという条件に見合った場合のみが残る。したがって，求める場合の数は (r,k)-(r-1,k) である。


さて，どちらのアプローチもおなじ場合の数を求めているのだから，

(r-,k-1)=(r,k)-(r-1,k)

が成り立つはずである。これは，Pascal の三角形として広く知られている漸化式

(r-1,k-1)+(r-1,k)=(r,k)

に他ならない。


異なる状況設定から同じ公式を導くというのは，ものの見方が広がったような心持になるので，楽しいものである。