별과 막대(Stars and bars)

똑같은 사탕 n개를 아이 k명에게 나눠 주는 방법은 몇 가지일까요? 사탕끼리는 구별하지 않고 아이끼리는 구별하며, 하나도 못 받는 아이가 있어도 됩니다. 사탕을 별 ★로, 아이 사이의 경계를 막대 |로 그리면 나눠 주기⁠(period)⁠ 하나가 별 n개와 막대 k−1개를 한 줄로 늘어놓은 것 하나가 됩니다. ★★|★||★★★은 네 아이에게 2, 1, 0, 3개를 준 것입니다.

사탕 개, 아이 명, . 다음 배치 무작위 배치 지금 배치는 입니다.

이 대응은 일대일대응입니다. 줄에는 자리가 $n+k-1$개 있고, 그중 막대가 설 $k-1$자리를 고르면 배치가 하나 정해지며, 배치마다 막대 자리가 하나씩 정해집니다. 그래서 방법의 수는 이항계수⁠(binomial coefficient)⁠ $\binom{n+k-1}{k-1}$입니다. 별과 막대를 늘어놓는 순열⁠(permutation)⁠로 보고 별끼리, 막대끼리의 순서를 무시해도 $\frac{(n+k-1)!}{n!\,(k-1)!}$로 같은 값이 나옵니다.

모두 하나 이상. 아이마다 적어도 하나씩 받아야 한다면, 별 n개 사이의 틈 n−1곳 가운데 k−1곳에 막대를 세우면 됩니다(한 틈에 막대 둘은 안 됩니다). 그래서 $\binom{n-1}{k-1}$가지입니다(n이 k보다 작으면 0가지). 먼저 하나씩 나눠 주고 남은 n−k개를 자유롭게 나누는 것과 같은 답입니다. 이것은 n을 k개의 자연수⁠(natural number)⁠의 순서 있는 합으로 쓰는 방법의 수이기도 합니다. 순서를 무시하면 분할수⁠(partition number)⁠가 되는데, 그쪽에는 이렇게 간단한 식이 없습니다.

다른 얼굴들. 똑같이 생긴 주사위 k개를 한꺼번에 던졌을 때 나올 수 있는 눈의 조합은, 눈 1~6이라는 상자 여섯 개에 주사위 k개를 나누는 것이므로 $\binom{k+5}{5}$가지입니다. 두 개면 21가지입니다. 하지만 이 21가지가 같은 확률⁠(probability)⁠로 나오지는 않습니다. (1, 2)는 (1, 1)보다 두 배 자주 나옵니다. 확률을 셀 때는 주사위를 구별해서 세야 한다는 점은 초기 확률론에서 자주 헷갈린 대목입니다. 1754년 달랑베르가 동전을 두 번 던져 앞면이 한 번이라도 나올 확률을, 경우를 '첫 번째 앞면', '뒤-앞', '뒤-뒤'의 셋으로 보고 2/3라고 쓴 것이 유명한 예입니다(네 경우를 구별해 세면 3/4입니다).

같은 수가 다른 곳에도 나옵니다. 변수 k개로 된 n차 단항식, 곧 $x_1^2 x_3$처럼 변수들의 거듭제곱을 곱하되 지수의 합이 n인 식 $x_1^{a_1}\cdots x_k^{a_k}$의 개수, 방정식 $a_1+\cdots+a_k = n$의 음이 아닌 정수⁠(integer)⁠해의 개수도 모두 같은 수입니다.

이어지는 곳. 생성함수⁠(generating function)⁠로 보면 아이 한 명은 $1 + x + x^2 + \cdots = \frac1{1-x}$(등비급수⁠, geometric series⁠)이고, k명은 $(1-x)^{-k}$이며 그 $x^n$ 계수가 바로 이 답입니다. n과 k를 바꿔 가며 표에 적으면 수들이 파스칼의 삼각형⁠(Pascal's triangle)⁠의 대각선을 따라 늘어섭니다. 거꾸로, 사탕이 아이보다 많으면 어떤 배치에서든 누군가는 둘 이상 받습니다. 모든 $x_i \le 1$인 배치가 없다는 이 말이 비둘기집 원리⁠(pigeonhole principle)⁠입니다.