핵심 질문: 순서가 중요한가?
순열과 조합은 모두 n개의 서로 다른 항목으로 이루어진 그룹에서 r개를 고르는 방법의 수를 세지만, 서로 다른 두 질문에 답합니다. 순열은 r개의 항목을 고르고 배열하는 방법의 수를 세므로, 같은 항목이라도 순서가 다르게 배열된 두 선택은 서로 다른 두 결과로 계산됩니다. 조합은 r개의 항목을 고르는 방법의 수만을 세므로, 같은 항목으로 이루어진 두 선택은 뽑힌 순서와 상관없이 하나의 결과로 계산됩니다.
어느 쪽이 적용되는지 판단하는 간단한 방법은 정확히 같은 항목을 사용하지만 순서나 배열이 다른 두 선택을 떠올려 보는 것입니다. 그 두 선택이 서로 다른 순위, 다른 비밀번호, 다른 경주 결승 순서처럼 실제로 다른 결과를 나타낸다면 순서가 중요한 것이며 순열이 올바른 계산법입니다. 그 두 선택이 같은 위원회, 같은 카드 패, 같은 복권 번호 세트처럼 실제로 같은 결과를 나타낸다면 순서는 중요하지 않으며 조합이 올바른 계산법입니다.
공식: nPr과 nCr, 그리고 검증된 예제
n개의 서로 다른 항목에서 r개를 고르는 순열의 수는 nPr = n! / (n − r)!이고, 조합의 수는 nCr = n! / [r! (n − r)!]입니다 — 조합 공식은 순열 공식을 r!으로 나눈 것인데, r!으로 나누는 이유는 순열에서는 서로 다른 결과로 취급하던, 같은 항목 그룹의 r! 가지 서로 다른 배열을 하나로 묶어 없애기 때문입니다.
예제 풀이: 7개짜리 그룹에서 3개의 항목을 고르는 경우입니다. 순열: 7P3 = 7! / (7−3)! = 7 × 6 × 5 = 210. 조합: 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35. 조합의 수는 정확히 순열의 수를 3! = 6으로 나눈 값이며, 이는 nCr = nPr / r!이라는 관계를 확인해 줍니다.
| 구분 | 공식 | n=7, r=3일 때의 값 |
|---|---|---|
| 순열 (순서 중요) | nPr = n! / (n − r)! | 7P3 = 7 × 6 × 5 = 210 |
| 조합 (순서 무관) | nCr = n! / [r!(n − r)!] | 7C3 = 210 / 3! = 35 |
중복 허용과 중복 불허
위의 두 공식은 모두 n개의 각 항목을 최대 한 번씩만 선택할 수 있다고 가정합니다. 즉 비복원 추출입니다. 항목을 다시 사용할 수 있을 때(복원 추출, 중복 추출이라고도 함)는 계산 공식이 달라집니다. 중복을 허용하는 순열은 단순히 n을 r제곱한 값입니다. r개의 위치 각각이 이전에 무엇을 선택했는지와 상관없이 독립적으로 n가지 선택지를 모두 가지기 때문입니다: n^r.
중복을 허용하는 조합은 다른 공식인 C(n + r − 1, r)을 사용합니다. 이는 중복이 허용되고 순서는 여전히 중요하지 않을 때 n가지 종류에서 r개를 고르는 방법의 수를 셉니다 — 이는 비교적 드물게 필요한 경우이지만, 예를 들어 n가지 맛의 아이스크림에서 같은 맛을 두 번 이상 고를 수 있는 상태로 스쿱을 고를 때 나타납니다.
| 경우 | 공식 | 전형적인 예 |
|---|---|---|
| 순열, 중복 없음 | n! / (n − r)! | 7명의 결선 진출자 중 3명의 순위를 정하기 |
| 순열, 중복 있음 | n^r | 숫자가 반복될 수 있는 4자리 PIN |
| 조합, 중복 없음 | n! / [r!(n − r)!] | 복권 번호 6개 고르기 |
| 조합, 중복 있음 | (n + r − 1)! / [r!(n − 1)!] | 5가지 아이스크림 맛에서 중복을 허용해 3스쿱 고르기 |
예제 풀이: PIN 코드와 복권
4자리 PIN은 4개의 자리 각각에 0에서 9까지의 숫자가 올 수 있고 숫자가 반복될 수 있는(일반적인 은행 PIN 규칙) 경우로, 중복이 있는 순열의 예입니다. 순서가 중요하고(1234와 4321은 서로 다른 PIN입니다) 중복이 허용되므로 가능한 PIN의 수는 10^4 = 10,000개입니다. 만약 숫자 반복이 허용되지 않는다면 그 수는 중복 없는 순열 값인 10P4 = 10 × 9 × 8 × 7 = 5,040으로 줄어듭니다 — 사용한 각 숫자가 남은 자리들에서 선택지를 하나씩 줄이기 때문에 가능한 경우의 수가 더 적습니다.
49개의 번호 중에서 6개를 뽑고, 번호가 중복되지 않으며 뽑힌 순서는 당첨 여부와 무관한 전형적인 복권 형식은 중복 없는 조합의 예입니다. C(49, 6) = 49! / (6! × 43!) = 13,983,816입니다. 이 큰 숫자는 바로 이런 복권 형식이 확률이 매우 낮은 게임으로 묘사되는 이유입니다 — n이 r에 비해 커질수록 조합의 수는 매우 빠르게 커지는데, 이는 작고 고정된 집합에서의 배열이 아니라 큰 모집단에서의 순서 없는 그룹을 세는 것이기 때문입니다.
어느 공식을 쓸지 빠르게 기억하는 방법
「순열(Permutation)」과 「위치(Position)」는 둘 다 P 발음으로 시작하는데, 순열은 위치 — 각 항목이 순서상 어디에 놓이는지 — 를 신경 쓴다는 유용한 기억법이 됩니다. 「조합(Combination)」은 가방 속 내용물이나 위원회처럼 결합된 하나의 그룹을 나타내며, 여기서는 오직 소속 여부만 중요할 뿐 추가된 순서는 중요하지 않습니다.
비밀번호, PIN, 경주 순위, 그리고 좌석 배치나 일정 배열은 모두 순열 문제입니다. 순서를 바꾸면 결과가 달라지기 때문입니다. 카드 패, 복권 번호 세트, 위원회 구성원, 그 밖의 순서 없는 그룹 선택은 모두 조합 문제입니다. 구성원만이 중요할 뿐 뽑힌 순서는 중요하지 않기 때문입니다.
자주 묻는 질문
순열과 조합의 차이는 무엇인가요?
순열은 순서가 중요한 배열의 수를 세므로, 같은 항목이라도 다른 순서로 고르면 다른 결과로 계산됩니다. 조합은 순서가 중요하지 않은 선택의 수를 세므로, 같은 항목은 어떤 순서로 고르든 하나의 결과로 계산됩니다. 둘 다 n개의 항목으로 이루어진 같은 그룹에서 시작해 그중 r개를 고르지만, 같은 n과 r에 대해 순열의 수는 항상 그에 대응하는 조합의 수보다 크거나 같습니다.
7P3은 무엇이고 어떻게 계산하나요?
7P3은 210이며, 순서가 중요한 상태로 7개의 서로 다른 항목으로 이루어진 그룹에서 3개를 고르고 배열하는 방법의 수입니다. 7P3 = 7! / (7 − 3)! = 7 × 6 × 5 = 210으로 계산되며, 7!의 가장 큰 세 인수를 곱하는 것과 같습니다. 더 작은 인수들은 분모의 (7−3)!과 약분되어 사라지기 때문입니다.
7C3은 무엇이고 어떻게 계산하나요?
7C3은 35이며, 순서가 중요하지 않은 상태로 7개의 서로 다른 항목으로 이루어진 그룹에서 3개를 고르는 방법의 수입니다. 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35로 계산됩니다 — 이는 정확히 순열의 수인 7P3 = 210을 3!(같은 3개 그룹을 재배열하는 방법의 수)로 나눈 값입니다. 조합은 같은 그룹의 모든 배열을 하나의 결과로 합치기 때문입니다.
PIN에는 왜 순열을 쓰고 복권에는 왜 조합을 쓰나요?
PIN은 1234와 4321을 서로 다른 코드로 취급하므로 숫자의 순서가 결과를 바꾸는 순열 상황입니다 — 일반적인 4자리 PIN처럼 중복을 허용하면 10^4 = 10,000가지가 됩니다. 복권 티켓은 뽑힌 번호가 무엇인지에만 따라 당첨이 결정되고 뽑힌 순서는 상관없으므로, 같은 번호를 다른 순서로 뽑아도 같은 당첨 결과가 되는 조합 상황입니다 — 49개 중 6개를 뽑는 형식에서는 C(49,6) = 13,983,816가지의 번호 조합이 가능합니다.
순열이나 조합 공식에서 「중복 허용」이란 무슨 뜻인가요?
같은 결과 안에서 한 항목을 두 번 이상 선택할 수 있다는 뜻입니다. 중복을 허용하는 순열은 n^r을 사용합니다(r개의 위치 각각이 독립적으로 n가지 선택지를 모두 가짐). 중복을 허용하는 조합은 (n + r − 1)! / [r!(n − 1)!]을 사용합니다. 중복이 없을 때는 각 항목을 최대 한 번만 사용할 수 있으며, 이것이 표준적인 nPr과 nCr 공식이 가정하는 상황입니다.
참고 자료
- NIST Digital Library of Mathematical Functions (DLMF), §26 Combinatorial Analysis. dlmf.nist.gov.
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018 (permutations, combinations, and counting with repetition).
- Ross SM. A First Course in Probability. Pearson (combinatorial counting methods).
- Weisstein EW. "Permutation" and "Combination." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.