Mathrao

【定理・公式・証明】高校数学定理・公式 – 数学A – 組み合わせ・ ${}_n \mathrm{ C }_k$ の性質

組合せ

異なる $n$ 個から $k$ 個を選ぶ組合せの総数は，

nCk=kPkk!\displaystyle _{n} C_{k} = \frac{_{k} P_{k}}{k!} (通り)

nCk_{n} C_{k} の性質①( nCk=nCn−k_{n} C_{k} = _{n} C_{n-k}

$n$ は自然数， $k$ は0以上の整数とする。 $0 \leqq k \leqq n$ において，

(Ⅰ) nCk=n!k!(n−k)!\displaystyle _{n} C_{k} = \frac{n!}{k!(n-k)!}

(Ⅱ) nCk=nCn−k_{n} C_{k} = _{n} C_{n-k}

nCk_{n} C_{k} の性質② ( k⋅nCk=n⋅n−1Ck−1k \cdot _{n} C_{k} =n \cdot _{n-1} C_{k-1} )

$n$ は2以上の整数， $1 \leqq k \leqq n$ において，

k⋅nCk=n⋅n−1Ck−1k \cdot _{n} C_{k} =n \cdot _{n-1} C_{k-1}

証明

k⋅nCk=k⋅n!k!⋅(n−k)!\displaystyle k \cdot _{n} C_{k} =k \cdot \frac{n!}{k! \cdot (n-k)!}

=k⋅n⋅(n−1)!k⋅(k−1)!⋅(n−k)!\displaystyle =k \cdot \frac{n \cdot (n-1)!}{k \cdot (k-1)! \cdot (n-k)!}

=n⋅(n−1)!(k−1)!(n−k)!\displaystyle = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!}

=n⋅(n−1)!(k−1)!⋅{(n−1)−(k−1)}!\displaystyle =n \cdot \frac{(n-1)!}{(k-1)! \cdot \{ (n-1)-(k-1) \}!}

n⋅n−1Ck−1n \cdot _{n-1} C_{k-1}

nCk_{n} C_{k} の性質③( nCk=n−1Ck−1+n−1Ck_{n} C_{k} = _{n-1} C_{k-1} + _{n-1} C_{k} )

$n$ は2以上の整数， $k$ は $1 \leqq k \leqq n-1$ を満たす整数とするとき，

nCk=n−1Ck−1+n−1Ck_{n} C_{k} = _{n-1} C_{k-1} + _{n-1} C_{k}

証明

n−1Ck−1+n−1Ck=(n−1)!(k−1)!{(n−1)−(k−1)}!+(n−1)!k!{(n−1)−k}!\displaystyle _{n-1} C_{k-1} + _{n-1} C_{k} = \frac{(n-1)!}{(k-1)! \{ (n-1)-(k-1) \} !} + \frac{(n-1)!}{k! \{ (n-1) -k \} !}

=(n−1)!(k−1)!(n−k)!+(n−1)!k!(n−k−1)!\displaystyle = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!}

=k(n−1)!k(k−1)!(n−k)!(n−1)!(n−k)k!(n−k)(n−k−1)!\displaystyle = \frac{k(n-1)!}{k(k-1)!(n-k)!} \frac{(n-1)!(n-k)}{k!(n-k)(n-k-1)!}

=k(n−1)!k!(n−k)!+(n−1)!(n−k)k!(n−k)!\displaystyle = \frac{k(n-1)!}{k!(n-k)!} + \frac{(n-1)!(n-k)}{k!(n-k)!}

=(n−1)!(k−n−k)k!(n−k)!\displaystyle = \frac{(n-1)!(k-n-k)}{k!(n-k)!}

=n(n−1)!k!(n−k)!\displaystyle = \frac{n(n-1)!}{k!(n-k)!}

=n!k!(n−k)!\displaystyle = \frac{n!}{k!(n-k)!}

=nCk= _{n} C_{k}