세는 방법의 기초

조합론은 ‘몇 가지인가’를 정확히 세는 수학이다. 합의 법칙과 곱의 법칙 외에도, 세기 어려운 대상을 세기 쉬운 대상과 일대일로 대응시켜 세는 방법이 조합론의 가장 강력한 도구이다.

핵심 개념

  • 합의 법칙, 곱의 법칙 (확률과 통계 ‘경우의 수’ 단원)
  • 일대일대응(전단사): 두 집합 사이에 짝이 빠짐없이 하나씩 맺어지면 두 집합의 원소의 개수가 같다.
  • 여사건으로 세기: (전체) − (조건을 만족하지 않는 것)
세 원소 집합의 부분집합 8개와 세 자리 이진수 000~111의 대응
부분집합 ↔ 이진수: 각 원소를 넣을지(1) 뺄지(0)를 적는다

핵심 정리

원소가 $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$
알림: 보호된 콘텐츠입니다.