>>586 板違いぎみだが。
n個の候補からr個選んでくる組合せは、
n個の候補をn-1個と1個にわけておくと、以下のいずれかになる。
(1) n-1個の候補からr個選んで、かつ、1個の候補は選ばない場合。
(2) n-1個の候補からr-1個選んで、かつ、1個の候補を選ぶ場合。
(1)の場合の組合せの数はn-1Cr、(2)の場合の組合せの数はn-1Cr-1だから、
これらの合計n-1Cr + n-1Cr-1がnCrに等しくなる。