2
異なるn個の要素から個とる組合せの総数 n Cr
は,1つの特定の要素αをr個の中に含むか含ま
ないかに分けると, 次のいずれかになる。
(i) α を含む場合の組合せは, n個の要素からαを
除いた (n-1) 個から (n-1) 個とる選び方があ
るから
n-1Cr-1
(ii) αを含まない場合の組合せは、n個の要素から
αを除いた (n-1)個から個とる選び方がある
から
n-1 Cr
(i), (ii) は同時には起こらないから,和の法則によ
り,nCr = n-1Cr-1+n-1C, が成り立つ。
C