[Discrete Mathematics] 경우의 수 및 순열과 조합

---

경우의 수

 

• 곱셈의 원리

어떤 시행이 연속된 $ t $ 단계로 구성되고, 각 단계가 $ n_1, n_2, \cdots, n_t $ 가지 방법으로 이뤄져 있을 때 서로 다른 시행의 가능한 모든 경우의 수는 다음과 같다.

$$ n_1 \times n_2 \times \cdots \times n_t $$

요약하면 객체들이 연속적인 단계로 구성되면 곱셈 원리를 사용한다.

 

• 덧셈의 원리

$ X_1, X_2, \cdots , X_t $ 가 집합이고 $ i $ 번째 집합 $ X_i $ 가 $ n_i $ 개의 원소를 가지고 있다 가정하자. 만약 $ \{ X_1, X_2, \cdots, X_t \} $ 가 서로소, 즉 $ i \neq j $ 일 때 $ X_i \cap X_j = \emptyset $ 이라 할 때 $ X_1 $ 또는 $ X_2 $ 또는 $ \dots $ 또는 $ X_t $ 에서 원소를 선택하는 경우의 수는 다음과 같다.

$$ n_1 + n_2 + \cdots + n_t $$

요약하면 객체들이 서로소인 집합으로 이뤄져 있다면 덧셈 원리를 사용한다.

 

• 포함-배제의 원리

$ X $ 와 $ Y $ 가 유한집합이면 다음이 성립한다.

$$ | X \cup Y | = | X | + | Y | - | X \cap Y | $$

 

---

순열 (Permutation)

 

$ n $ 개의 서로 다른 원소의 순열은 $ n $ 개의 원소의 순서를 정하는 것이다. 예를 들어 $ \{ a, b, c \} $ 가 있다고 하면 $ abc, acb, bac, bca, cab, cba $ 가 순열이고, 총 $ 6 $ 개이다. 순열의 수는 $ n! $ 이다.

순열의 수가 $ n ! $ 인 이유는 곱셈 원리를 이용하여 증명 가능한데, $ n $ 개 원소의 순서를 정하는 방법은 첫 번째 순서를 정하고, 두 번째 순서를 정하고, ..., 마지막 순서를 정하는 식으로 생각할 수 있다. 따라서 첫 번째 순서를 정하는 방법의 수는, 즉 $ n $ 개 중 하나를 고르는 경우의 수는 $ n $ 이고, 두 번째 순서를 정하는 방법은 첫 번째 순서로 뽑은 원소를 제외한 $ n - 1 $ 이다. 반복하여 곱하면 $ n ! $ 이 된다는 것을 알 수 있다.

 

---

$ r $-순열 

 

$ n $ 개의 서로 다른 원소의 $ r $-순열은 $ n $ 개의 원소에서 $ r $ 개의 원소를 가진 부분집합의 순서를 정하는 것이다. $ r $-순열의 수는 $ P(n, r) $ 이다.

$$ P(n, r) = \dfrac{n!}{(n-r)!} $$

 

---

$ r $-조합

 

$ n $ 개의 서로 다른 원소의 $ r $-조합은 $ n $ 개의 원소에서 $ r $ 개의 원소를 순서에 상관없이 선택하는 것이다. $ r $-조합의 수는 $ C(n, r) $ 혹은 $ \dbinom{n}{r} $ 이다.

$$ C(n, r) = \dbinom{n}{r} = \dfrac{P(n, r)}{r!} = \dfrac{n!}{(n-r)! r!} $$

 

---

순열과 조합 생성을 위한 알고리즘

 

사전식 순서는 알파벳뿐 아니라 기호 집합에서 순서를 정의한 것이다. $ \alpha = s_1 s_2 \cdots s_p $ 와 $ \beta = t_1 t_2 \cdots t_q $ 가 $ \{ 1, 2, \dots, n \} $ 의 문자열이라 할 때 $ p < q $ 이고 모든 $ i = 1, 2, \dots, p $ 에 대해 $ s_i = t_i $ 이면, 혹은  $ s_i \neq t_i $ 인 $ i $ 가 존재하면서 그런 $ i $ 중 가장 작은 $ i $ 에 대해 $ s_i < t_i $ 이면 $ \alpha $ 가 $ \beta $ 보다 사전식 배열 상 작다고 한다.

$ r $-조합 $ \{ x_1, \dots, x_r \} $ 은 문자열 $ s_1, \dots, s_r $ 로 표현되는데, 여기서 $ s_1 < s_2 < \cdots < s_r $ 이고 $ \{ x_1, \dots , x_r \} = \{ s_1, \dots, s_r \} $ 이다. 만약 $ \{ 1, 2, \dots, n \} $ 의 모든 $ r $-조합을 사전식으로 나열하면 $ 12\cdots r, \dots, (n-r+1) \cdots n $ 으로 나열할 수 있다.

다음 조합 생성 알고리즘은 $ \{ 1, 2, \dots, n \} $ 의 모든 $ r $-조합을 사전식 오름차순(increasing lexicographic order)으로 나열한다.

입력: $ r $, $ n $
출력: 사전식 오름차순으로 정렬된 모든 $ r $-조합

combination(r, n) {
    for i = 1 to r {
        s[i] = i
    }
    print(s[1], ..., s[r])
    for i = 2 to C(n, r) {
        m = r
        max_val = n
        while (s[m] == max_val) {
            m = m - 1
            max_val = max_val - 1
        }
        s[m] = s[m] + 1
        for j = m + 1 to r {
            s[j] = s[j-1] + 1
        }
        print(s[1], ..., s[r])
    }
}