[이산수학] 경우의 수, 순열, 조합

경우의 수

합의 법칙

합의 법칙 (rule of sum)
두 사건 $A$, $B$가 일어날 경우의 수

$$ n(A \cup B) = n(A) + n(B) = m + n $$

 

곱의 법칙

곱의 법칙 (rule of product)
두 사건 $A$, $B$가 동시에 일어날 경우의 수

$$ n(A \cap B) = n(A) \times n(B) = m \cdot n $$

 

순열

순열 (permutation)
서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것.

서로 다른 $n$개의 원소 중 $r$개를 택하는 순열의 수: $_nP_r$

$$ _nP_r = n \times (n - 1) \times (n - 2) \times \cdots \times (n - r + 1) $$

 

조합

조합 (combination)
서로 다른 원소 중 순서를 생각하지 않고 배열하는 것.

서로 다른 $n$개의 원소 중 순서를 생각하지 않고 $r$개를 택하는 조합의 수: $_nC_r$

$$ _nC_r = {_nP_r \over r!} = {n \times (n - 1) \times (n - 2) \times \cdots \times (n - r + 1) \over r \times (r - 1) \times (r - 2) \times \cdots \times 3 \times 2 \times 1} = {n! \over r!(n - r)!} $$