01 경우의 수

핵심 서로 다른 $n$개를 원형으로 배열하는 경우의 수는 $(n-1)!$. 회전하여 같아지는 것을 하나로 보기 때문에 $\dfrac{n!}{n}=(n-1)!$이 된다.

역사 순서를 따지는 셈은 17세기 파스칼·페르마의 조합론에서 체계화되었지만, 원형 배열·목걸이처럼 ‘돌리거나 뒤집어 같아지는’ 대칭을 세는 문제는 더 미묘하다. 이런 대칭의 셈은 훗날 군론과 조합론이 만나는 자리가 되었다.

핵심 서로 다른 $n$개에서 중복을 허락해 $r$개를 택해 나열하는 경우의 수 $_{n}\Pi_{r}=n^{r}$.

역사 비밀번호나 모스 부호처럼 ‘같은 것을 또 써도 되는’ 배열의 셈이다. $n^{r}$이라는 폭발적 증가는 정보의 양을 가늠하는 척도가 되어, 자릿수와 경우의 수로 정보를 재는 현대 정보이론의 직관과 맞닿는다.

핵심 $n$개 중 같은 것이 각각 $p,q,\dots$개씩 있을 때 일렬로 나열하는 경우의 수 $\dfrac{n!}{p!\,q!\,\cdots}$.

역사 같은 글자가 섞인 단어의 배열을 세는 이 셈법은 인도 수학의 오랜 전통이다. 이는 곧 다항정리의 계수와 같으며, ‘구별되지 않는 것을 어떻게 셀까’라는 물음은 통계역학에서 입자를 세는 방식으로까지 이어진다.

핵심 서로 다른 $n$개에서 중복을 허락해 순서 없이 $r$개를 택하는 경우의 수 $_{n}\mathrm{H}_{r}={}_{n+r-1}\mathrm{C}_{r}$.

역사 “사탕 $r$개를 $n$종류에서 고르기”처럼 중복을 허락해 ‘묶음으로’ 고르는 셈이다. 칸막이와 공으로 바꿔 세는 기발한 방법(작대기와 별)은, 겉보기에 다른 문제를 같은 구조로 바꾸는 조합론적 사고의 묘미를 보여 준다.

핵심 $(a+b)^{n}=\displaystyle\sum_{r=0}^{n}{}_{n}\mathrm{C}_{r}\,a^{n-r}b^{r}$. 계수 $_{n}\mathrm{C}_{r}$가 파스칼의 삼각형을 이룬다.

역사 $(a+b)^{n}$의 전개 계수가 조합의 수라는 이항정리는, 13세기 중국 양휘와 페르시아 수학자들이 알던 파스칼의 삼각형으로 정리된다. 뉴턴은 이를 지수가 분수·음수인 경우까지 일반화해(일반화 이항정리) 미적분의 무한급수로 이어 갔다.