← 목록으로 돌아가기
1. 경우의 수란?
경우의 수는 어떤 사건이 일어날 수 있는 모든 가능한 경우의 개수를 의미합니다.
이산수학에서 가장 중요한 개념 중 하나로, 순열(Permutation)과
조합(Combination)이 대표적인 방법입니다.
2. 순열 (Permutation)
순열은 순서가 있는 배열을 의미합니다.
서로 다른 \(n\)개에서 \(r\)개를 선택하여 순서대로 나열하는 경우의 수입니다.
예시: A, B, C 세 사람이 앉을 수 있는 의자가 2개 있을 때, 앉는 방법의 수는?
ABC → AB, BA, AC, CA, BC, CB = 6가지
\(P(3, 2) = \frac{3!}{1!} = 6\)
3. 조합 (Combination)
조합은 순서가 없는 선택을 의미합니다.
서로 다른 \(n\)개에서 순서에 상관없이 \(r\)개를 선택하는 경우의 수입니다.
조합 공식:
$$C(n, r) = {}_nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$
예시: A, B, C 세 사람 중 2명을 선택하는 방법의 수는?
AB, AC, BC = 3가지 (AB와 BA는 같음)
\(C(3, 2) = \frac{3!}{2! \cdot 1!} = 3\)
4. 순열과 조합의 비교
| 구분 |
순열 (Permutation) |
조합 (Combination) |
| 순서 |
순서 중요 O |
순서 중요 X |
| 공식 |
\(\frac{n!}{(n-r)!}\) |
\(\frac{n!}{r!(n-r)!}\) |
| 경우의 수 |
많음 |
적음 |
| 관계 |
\(P(n,r) = r! \times C(n,r)\) |
\(C(n,r) = \frac{P(n,r)}{r!}\) |
| 예시 |
비밀번호, 순위, 좌석배치 |
팀 구성, 메뉴 선택 |
핵심 구분 포인트:
"AB와 BA를 다르게 본다" → 순열
"AB와 BA를 같게 본다" → 조합
5. 연습문제
문제 1. 10명의 학생 중에서 회장 1명, 부회장 1명을 선출하는 경우의 수를 구하시오.
풀이 1.
회장과 부회장은 역할이 다르므로 순서가 중요합니다. 따라서 순열을 사용합니다.
10명 중 2명을 순서를 고려하여 선택:
$$P(10, 2) = \frac{10!}{8!} = 10 \times 9 = 90$$
답: 90가지
문제 2. 10명의 학생 중에서 청소 당번 2명을 선발하는 경우의 수를 구하시오.
풀이 2.
청소 당번은 역할이 동일하므로 순서가 중요하지 않습니다. 따라서 조합을 사용합니다.
10명 중 2명을 순서 없이 선택:
$$C(10, 2) = \frac{10!}{2! \times 8!} = \frac{10 \times 9}{2 \times 1} = 45$$
답: 45가지
문제 3. 서로 다른 5권의 책 중에서 3권을 선택하여 책꽂이에 나란히 꽂는 경우의 수를 구하시오.
풀이 3.
책을 책꽂이에 꽂는 것은 배열 순서가 중요합니다. (왼쪽부터 A-B-C와 C-B-A는 다름)
따라서 순열을 사용합니다.
5권 중 3권을 선택하여 순서대로 배열:
$$P(5, 3) = \frac{5!}{2!} = 5 \times 4 \times 3 = 60$$
답: 60가지
참고: 만약 "3권을 선택만 한다"면 조합 \(C(5,3) = 10\)가지입니다.
문제 4. 0, 1, 2, 3, 4 다섯 개의 숫자 카드가 있다. 이 중 3장을 뽽아 만들 수 있는 세 자리 자연수의 개수를 구하시오. (단, 같은 숫자는 중복 사용 불가)
풀이 4.
세 자리 수는 배열 순서가 중요하므로 순열 문제입니다.
그러나 백의 자리에는 0이 올 수 없다는 조건이 있습니다.
방법 1: 경우를 나누기
전체 순열에서 백의 자리가 0인 경우를 제외:
• 전체 경우: 5개 중 3개를 순서대로 배열
$$P(5, 3) = 5 \times 4 \times 3 = 60$$
• 백의 자리가 0인 경우: 나머지 4개 중 2개를 배열
$$P(4, 2) = 4 \times 3 = 12$$
• 세 자리 자연수: \(60 - 12 = 48\)
방법 2: 자리별로 계산
• 백의 자리: 1, 2, 3, 4 중 선택 → 4가지
• 십의 자리: 백의 자리에서 선택한 것 제외한 4개 중 선택 → 4가지
• 일의 자리: 이미 선택한 2개 제외한 3개 중 선택 → 3가지
$$4 \times 4 \times 3 = 48$$
답: 48가지
6. 마무리
순열과 조합의 핵심은 "순서가 중요한가?"를 판단하는 것입니다.
실생활 문제를 접했을 때 이 질문을 먼저 던져보면 어떤 공식을 사용해야 할지 쉽게 결정할 수 있습니다.
문제 해결 체크리스트:
1. 순서가 중요한가? → Yes: 순열, No: 조합
2. 전체 개수와 선택 개수는?
3. 특별한 조건은 없는가? (중복, 제한 조건 등)
4. 공식 적용 후 조건에 맞지 않는 경우 제외