とある大学の入試問題に次のような問題があった。
<問題>
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)
に他ならない。
異なる状況設定から同じ公式を導くというのは,ものの見方が広がったような心持になるので,楽しいものである。