典型90 015 - Don't be too close(★6)
解説の数え上げパート(下)がなかなか理解できなかったのでメモ。
小問題:1 から N までの整数が書かれた、N 個のボールがある。差がk以上となるようにa個のボールを選ぶ方法は何通りか?
答:$ _{N-(k-1)(a-1)} C _{a} 通り
理由:
N個の中から選んだ3個のボール("☑")に、α、β、γと名前を付ける。αの右隣2つと、βの右隣2つは、常に必ず選べないボールである。図では"-"で表されている。
図の"-"で表されている部分を取り除いて見ると、"☑"3つと"?"2つを並び替えた場合と同じになっている。
"☑"と"?"の合計数は$ _{N-(k-1)(a-1)} で、"☑"の数は $ a 。よって場合の数は $ _{N-(k-1)(a-1)} C _{a} 通り。