06 경우의 수

핵심 동시에 일어나지 않으면 더하고(합의 법칙), 잇따라 일어나면 곱한다(곱의 법칙). 모든 순열·조합 계산의 기본 원리다.

역사 경우의 수를 따지는 일은 도박과 함께 자랐다. 17세기 파스칼과 페르마가 도박의 분배 문제를 두고 주고받은 편지에서 확률론이 태어났고, 그 바탕에 ‘몇 가지 경우가 있는가’를 빠짐없이·중복 없이 세는 셈법이 있었다.

핵심 서로 다른 $n$개에서 $r$개를 골라 순서대로 나열하는 경우의 수 $_{n}\mathrm{P}_{r}=\dfrac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)$. 특히 $_{n}\mathrm{P}_{n}=n!$.

역사 순서를 따지는 배열의 셈은 고대 인도·중국에서도 다뤄졌다. 계승 기호 $n!$과 $_{n}\mathrm{P}_{r}$ 표기는 19세기에 정착했으며, 순열은 갈루아의 군론에서 ‘대상을 뒤섞는 대칭’으로 추상화되어 방정식 해법의 비밀을 풀었다.

핵심 서로 다른 $n$개에서 순서 없이 $r$개를 고르는 경우의 수 $_{n}\mathrm{C}_{r}=\dfrac{_{n}\mathrm{P}_{r}}{r!}=\dfrac{n!}{r!(n-r)!}$. $_{n}\mathrm{C}_{r}={}_{n}\mathrm{C}_{n-r}$ 등의 성질이 있다.

역사 조합의 수는 파스칼의 삼각형으로 정리되는데, 이 삼각형은 파스칼보다 훨씬 앞서 중국의 양휘(13세기)와 페르시아 수학자들이 알고 있었다. 이항정리의 계수이자 확률 계산의 핵심으로, 조합은 현대 통계의 토대가 된다.