조합론은 ‘몇 가지인가’를 정확히 세는 수학이다. 합의 법칙과 곱의 법칙 외에도, 세기 어려운 대상을 세기 쉬운 대상과 일대일로 대응시켜 세는 방법이 조합론의 가장 강력한 도구이다.
핵심 개념
- 합의 법칙, 곱의 법칙 (확률과 통계 ‘경우의 수’ 단원)
- 일대일대응(전단사): 두 집합 사이에 짝이 빠짐없이 하나씩 맺어지면 두 집합의 원소의 개수가 같다.
- 여사건으로 세기: (전체) − (조건을 만족하지 않는 것)
핵심 정리
원소가 $n$개인 집합의 부분집합은 $2^n$개이다.
증명 보기
방법 1 (곱의 법칙). 부분집합을 만들 때 각 원소마다 ‘넣는다/뺀다’ 두 가지를 고른다. $n$개의 원소에 대해 독립적으로 고르므로 $2\times2\times\cdots\times2=2^n$가지이다.
방법 2 (일대일대응). 원소를 $a_1,\dots,a_n$으로 정하고, 부분집합 $A$에 대해 $a_i\in A$이면 $i$번째 자리를 $1$, 아니면 $0$으로 하는 $n$자리 이진수를 대응시킨다. 서로 다른 부분집합은 서로 다른 이진수로, 모든 이진수는 어떤 부분집합에서 나오므로 일대일대응이다. $n$자리 이진수는 $2^n$개이다. $\blacksquare$
예제
- 원소가 $4$개인 집합의 부분집합 중 특정 원소 $a$를 포함하는 것: $a$는 반드시 넣고 나머지 $3$개만 고르므로 $2^3=8$개
- $1$부터 $1000$까지의 수 중 $0$이 하나도 없는 수: 한 자리 $9$개, 두 자리 $81$개, 세 자리 $729$개, 합 $819$개
확인 문제
$5\times5$ 격자에서 왼쪽 아래 모퉁이에서 오른쪽 위 모퉁이까지 오른쪽과 위쪽으로만 가는 최단경로의 수를 구하시오.
풀이 보기
모든 최단경로는 ‘오른쪽’ $5$번과 ‘위’ $5$번으로 이루어진 길이 $10$인 문자열과 일대일대응이다. 그런 문자열은 $10$자리 중 ‘오른쪽’의 자리 $5$개를 고르는 방법과 같으므로 ${}_{10}C_5=252$가지이다.
정리
- 세기 어려우면 세기 쉬운 것과 일대일로 짝지어 센다.
- 부분집합의 개수 $2^n$
