홍라이프 계산기순열과 조합 계산기 쉽게 이해하기 — 개념과 원리
순열과 조합은 서로 다른 n개 중에서 r개를 고르는 방법의 수를 셉니다. 순열(nPr)은 금·은·동메달을 정하는 것처럼 순서를 구별하고, 조합(nCr)은 위원 뽑기나 로또 번호처럼 순서를 구별하지 않습니다. 이 계산기는 두 값과 함께 중복순열, 중복조합도 보여 주므로 확률 문제, 비밀번호 경우의 수, 자리 배치 같은 상황에 맞는 값을 고를 수 있습니다.
계산 방법
- 순열: nPr = n! ÷ (n − r)! = n × (n − 1) × … × (n − r + 1)입니다.
- 조합: nCr = n! ÷ (r!(n − r)!) = nPr ÷ r!입니다.
- 중복순열: nʳ입니다. r개의 자리마다 n가지를 고를 수 있습니다. 교과서에서는 nΠr로 씁니다.
- 중복조합: nHr = (n + r − 1)Cr입니다.
순열과 조합에서 n, r은 0 ≤ r ≤ n인 정수입니다.
원리
순서가 있는 선택에서는 첫 번째에 n가지, 두 번째에 n − 1가지, 이렇게 r번 고르므로 모두 곱하면 nPr입니다. 이 목록에서 같은 r개로 이루어진 묶음은 순서만 바뀐 채 r!번씩 나타나므로 r!로 나누면 조합의 수가 남습니다. 중복을 허락하면 매번 n가지를 모두 고를 수 있어 nʳ이 됩니다. 중복조합은 "별과 막대" 방법으로 이해할 수 있습니다. n종류에서 r개를 고르는 것은 별 r개와 칸막이 n − 1개를 한 줄로 늘어놓는 것과 같으므로 (n + r − 1)Cr가지입니다.
예제 풀이
- 입력값: n = 10, r = 3입니다.
- nPr = 10 × 9 × 8 = 720입니다.
- nCr = 720 ÷ 3! = 720 ÷ 6 = 120입니다.
- 중복순열: 10³ = 1,000입니다(000부터 999까지의 세 자리 번호).
- 중복조합: 10H3 = 12C3 = 12 × 11 × 10 ÷ 6 = 220입니다.
결과 해석
순서가 중요한지, 같은 것을 여러 번 고를 수 있는지 두 가지를 물어보면 네 결과 중 무엇을 쓸지 정해집니다. 각 조합은 r!가지로 줄 세울 수 있으므로 순열은 항상 조합보다 크거나 같습니다. 조합은 nCr = nC(n − r)로 대칭이어서, 10개 중 3개를 고르는 수와 7개를 빼는 수가 같습니다. 특정한 조합 하나가 나올 확률은 1 ÷ nCr이며, 45개 중 6개를 고르는 로또라면 8,145,060분의 1입니다.
흔한 실수
- 순서가 없는 위원 선출이나 로또 번호에 순열을 쓰는 경우입니다.
- r!로 나누는 것을 잊어 r!배만큼 많이 세는 경우입니다.
- "BOOK"의 O처럼 같은 것이 섞여 있는데 서로 다른 것의 공식을 그대로 쓰는 경우입니다. 같은 것의 개수만큼 팩토리얼로 나누어야 합니다.
- 중복이 안 되는데 nʳ을 쓰거나, 중복이 되는데 nPr을 쓰는 경우입니다.
자주 묻는 질문
nPr과 nCr의 차이를 한 줄로 말하면 무엇인가요?
nPr은 순서를 구별한 경우의 수, nCr은 구별하지 않은 경우의 수이며 nPr = nCr × r!입니다.
nC0과 nCn은 얼마인가요?
둘 다 1입니다. 아무것도 고르지 않는 방법과 전부 고르는 방법은 각각 한 가지입니다.
포커 다섯 장 패의 경우의 수는 얼마인가요?
패는 순서가 없으므로 52C5 = 2,598,960가지입니다.
출처: Donald E. Knuth, The Art of Computer Programming, Vol. 1, §1.2.6 (Binomial Coefficients) · R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, 2nd ed., 1994, Chapter 5