경우의 수 세기

몇 가지 방법이 있는가#

앞선 글에 우리는 유리함수와 무리함수의 그래프를 탐구했다. 점근선을 따라 그래프가 어떻게 뻗어 나가는지 살펴봤다.

이 글에서는 전혀 다른 질문으로 출발한다. "몇 가지 방법이 있을까?" — 초6 때 나무 그림으로 경우를 세던 기억 나는가? 이 글에서는 그 아이디어를 훨씬 더 큰 수에 쓸 수 있는 공식으로 일반화한다.

나무 그림 → 표 → 공식, 세 가지 표상을 오가며 발견한다.

팩토리얼 — 차례대로 곱하기#

먼저 간단한 질문이다. 학생 3명(A, B, C)이 달리기 시합을 한다. 1등·2등·3등에 세 명이 줄 서는 방법은 몇 가지일까?

나무 그림으로 세어 본다.

A가 1등일 때 2가지, B가 1등일 때 2가지, C가 1등일 때 2가지 → 전체 3 × 2 × 1 = 6가지이다.

이 패턴에는 이름을 붙인다. 1부터 어떤 수까지 차례로 모두 곱한 것을 팩토리얼(factorial)이라 하고 느낌표 ! 로 쓴다.

특별히 0! = 1로 약속한다. 이유는 아래 조합 공식에서 자연스럽게 확인한다.

n명을 일렬로 세우는 방법의 수는 n! — 첫 자리에 n가지, 다음 자리에 (n-1)가지, …, 마지막에 1가지를 차례로 곱한 결과이다.

순열 — 순서가 중요할 때#

이번엔 학생 5명(A, B, C, D, E) 중에서 2명만 뽑아 1등·2등 메달을 준다. 가능한 배치 수를 세어 본다.

전체: 5 × 4 = 20가지이다.

이렇게 순서를 고려하여 n개 중 r개를 고르는 경우의 수를 순열(Permutation)이라 하고 ₙPᵣ로 쓴다.

순열 공식:

$$_nP_r = \frac{n!}{(n-r)!}$$

이 식은 n개 중 r개를 순서 있게 뽑을 때, 뒤에 남는 (n-r)!만큼의 곱을 제외한다는 뜻이다.

₅P₂ = 5! ÷ (5-2)! = 5! ÷ 3! = (5 × 4 × 3 × 2 × 1) ÷ (3 × 2 × 1) = 5 × 4 = 20

공식의 의미: n명 전체를 줄 세우는 n!에서, 선택하지 않는 뒷자리 (n-r)명의 순서 (n-r)!을 나눠 지운 것이다. 앞 r자리의 순서 있는 배치만 남는다.

특별한 경우:

• ₃P₃ = 3! ÷ 0! = 6 ÷ 1 = 6 (3명 전체 줄 세우기 — 0! = 1로 약속하는 이유)
• ₅P₁ = 5! ÷ 4! = 5 (5명 중 1명 고르기 — 당연히 5가지)

조합 — 순서가 상관없을 때#

이번엔 질문을 살짝 바꾼다. 학생 5명 중에서 2명을 팀원으로 뽑는다. 메달이 아니라 팀이라 순서가 없다. A-B 팀과 B-A 팀은 같은 팀이다.

순열로 구한 20가지 중에서, 2명을 뽑으면 그 2명끼리 순서 바꾸기가 2! = 2가지씩 겹친다. 그러니 순열 20가지를 2!로 나누면 순서를 무시한 팀의 수가 나온다.

20 ÷ 2! = 20 ÷ 2 = 10가지

이렇게 순서를 무시하고 n개 중 r개를 고르는 경우의 수를 조합(Combination)이라 하고 ₙCᵣ로 쓴다.

조합 공식:

$$_nC_r = \frac{n!}{r!,(n-r)!}$$

순서가 사라지면 같은 묶음이 r!번씩 중복되므로, 순열에서 그 중복을 한 번 더 나누어야 한다.

₅C₂ = 5! ÷ (2! × 3!) = 120 ÷ (2 × 6) = 120 ÷ 12 = 10

나열로 확인한다. 5명(A~E) 중 2명 조합:

4 + 3 + 2 + 1 = 10가지. 공식과 일치한다.

조합의 대칭 성질:

ₙCᵣ = ₙC(n-r)

₅C₂ = ₅C₃ = 10. 왜냐하면 2명을 고르는 것은 나머지 3명을 제외하는 것과 같기 때문이다.

특별한 경우:

• ₙC₀ = 1 (아무도 안 고르는 방법은 딱 1가지)
• ₙCₙ = 1 (전원 고르는 방법도 딱 1가지)
• ₙC₁ = n (1명 고르기는 n가지)

순열 vs 조합 — 핵심 판단법#

가장 중요한 판단 기준은 딱 하나이다: 순서가 중요한가?

핵심 관계:

$$_nC_r = \frac{_nP_r}{r!}$$

조합은 먼저 순서 있게 세고, 같은 선택을 순서만 바꿔 센 r!개의 중복을 제거한 값으로 읽는다.

조합은 순열을 r!로 나눈 것이다. 순열에서 "같은 묶음"의 중복을 r!로 제거한 결과이다.

공식 한눈에 보기#

관계: ₙCᵣ = ₙPᵣ ÷ r!

핵심 공식 정리#

• 팩토리얼 n!은 1부터 n까지 차례로 모두 곱한 값. 5! = 120, 0! = 1(약속).
• 순열 ₙPᵣ은 n개 중 r개를 순서 있게 고르는 경우의 수. n! ÷ (n-r)!
• 조합 ₙCᵣ은 n개 중 r개를 순서 없이 고르는 경우의 수. n! ÷ (r!(n-r)!)
• 판단 기준: 역할·위치가 구분되면 순열, 아니면 조합