1. 조합분석(Combinatorial Analysis)

영한 번역 키워드

• Counting: 계수
• Permutation: 순열
• Combination: 조합
• Multinomial Coefficient: 다항 계수
• Integer Solution: 정수 해
• Distinct: 서로 다른
• Indistinguishable: 구별할 수 없는
• Repetition: 중복

---

1. The Basic Principle of Counting (기본 계수 원리)

기본 원리: 어떤 일이 일어나기 위한 전체 경우의 수는 각 단계의 선택 경우의 수를 곱하여 계산한다.

• 곱의 법칙 (Multiplication Rule): 하나의 작업이 $n$ 가지 방법으로, 다음 작업이 $m$ 가지 방법으로 이루어진다면, 전체 작업은 $n \times m$ 가지 방법이 있다.
• 합의 법칙 (Addition Rule): 두 사건이 동시에 일어날 수 없다면, 각 사건의 경우의 수를 더해 전체 경우의 수를 구할 수 있다.

---

2. Permutations (순열)

정의: 서로 다른 $n$개 중에서 $r$개를 뽑아 순서를 고려하여 나열하는 경우의 수

• 공식: $P(n, r) = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n - r)!}$

• 중복 순열: 중복을 허용하는 순열은 $n^r$

• 같은 것이 포함된 순열: 동일한 것이 포함된 전체 순열은 $\frac{n!}{n_1! n_2! \cdots n_k!}$ (예: LETTER의 순열에서 T가 2개)

---

3. Combinations (조합)

정의: 서로 다른 $n$개 중에서 $r$개를 순서 없이 선택하는 경우의 수

• 공식: $C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

• 중복 조합: 중복을 허용하는 조합의 경우 $\binom{n + r - 1}{r}$ (예: 사탕 3개를 5종류 중에서 고르는 경우)

---

4. Multinomial Coefficients (다항 계수)

정의: $n$개의 항을 $k$개의 그룹으로 나누는 방법

• 공식: $\binom{n}{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!}$ (단, $n_1 + n_2 + \cdots + n_k = n$)

• 예시: 10명을 3, 4, 3명으로 나누는 경우

---

5. The Number of Integer Solutions of Equations (정수 해의 개수)

문제 유형: $x_1 + x_2 + \cdots + x_r = n$의 정수 해 개수

• 자연수 해 (Positive integers): $\binom{n - 1}{r - 1}$

• 0 이상의 정수 해 (Non-negative integers): $\binom{n + r - 1}{r - 1}$

• 응용: 동전 나누기, 사탕 분배 문제 등