이항계수(Binomial coefficient)

격자의 왼쪽 아래 모서리에서 출발해 오른쪽(→)이나 위(↑)로만 한 칸씩 움직여 목표 점까지 가는 가장 짧은 길을 셉니다. 전체 걸음 수를 $n =$ , 그중 오른쪽 걸음 수를 $k =$ 로 두면 목표는 $(k,\ n-k)$입니다. 노란 길은 그 가운데 하나, 입니다. 다른 길

길 하나는 n개의 걸음 자리 가운데 어느 k자리에 →를 놓을지 정하는 일과 같습니다. 그래서 길의 수는 n개 중 k개를 고르는 방법의 수, 곧 이항계수 $\binom nk$입니다. 고른 자리들의 집합⁠(set)⁠만 중요하고 고른 순서는 상관없으니, n개를 한 줄로 세우는 $n!$가지 순열⁠(permutation)⁠을 고른 쪽 안의 순서 $k!$와 남은 쪽 안의 순서 $(n-k)!$로 나눕니다. →와 ↑의 역할을 바꾸면 $\binom nk = \binom n{n-k}$도 저절로 보입니다.

격자의 각 점에 적힌 수는 그 점까지 가는 길의 수입니다. 어떤 점에 도착하는 길의 마지막 걸음은 →이거나 ↑이므로, 왼쪽 점의 수와 아래 점의 수를 더하면 됩니다. 이것이 파스칼의 법칙⁠(Pascal's rule)⁠ $\binom nk = \binom{n-1}{k-1} + \binom{n-1}{k}$이고, 격자를 45° 돌려 세우면 이 수들이 그대로 파스칼의 삼각형⁠(Pascal's triangle)⁠이 됩니다. 작은 칸의 답을 표에 적어 두고 더해 큰 칸의 답을 얻는 이 방식은 동적 계획법⁠(dynamic programming)⁠의 가장 단순한 예입니다.

이항정리⁠(binomial theorem)⁠. $(a+b)^n = (a+b)(a+b)\cdots(a+b)$를 전개하면 각 괄호에서 $a$나 $b$를 하나씩 골라 곱한 항들이 나옵니다. $a$를 정확히 k번 고르는 방법이 $\binom nk$가지이므로 $a^k b^{n-k}$의 계수가 이항계수입니다. 거꾸로 보면 $(1+x)^n$은 수열 $\binom n0, \binom n1, \ldots$을 계수로 담은 다항식⁠(polynomial)⁠인데, 이렇게 수열을 급수⁠(series)⁠의 계수로 담아 세는 방법을 생성함수⁠(generating function)⁠라 합니다. $a = b = 1$을 넣으면 $\sum_k \binom nk = 2^n$, 원소⁠(element)⁠가 n개인 집합의 부분집합⁠(subset)⁠ 전체, 곧 멱집합⁠(power set)⁠의 크기입니다(지금 ).

1665년 무렵 뉴턴은 지수가 정수⁠(integer)⁠가 아닐 때에도 $(1+x)^\alpha = 1 + \alpha x + \frac{\alpha(\alpha-1)}{2}x^2 + \cdots$가 성립함을 알아냈습니다(|x| < 1일 때). 이때는 항이 끝나지 않고 무한히 이어지는데, 이것이 $(1+x)^\alpha$의 테일러 급수⁠(Taylor series)⁠입니다. 예를 들어 α = 1/2이면 $\sqrt{1+x} = 1 + \tfrac12 x - \tfrac18 x^2 + \cdots$입니다.

확률⁠(probability)⁠로. 동전을 n번 던져 앞면이 k번 나오는 결과는 →↑ 길처럼 $\binom nk$개이고, 결과 하나하나의 확률이 $1/2^n$이므로 그 확률은 $\binom nk / 2^n$입니다. 이 값들을 k마다 늘어놓은 것이 이항분포⁠(binomial distribution)⁠이고, →를 +1, ↑를 −1로 읽으면 길은 무작위 행보⁠(random walk)⁠의 자취가 됩니다. n이 크면 계승⁠(factorial)⁠ 계산이 버거운데, 스털링 공식⁠(Stirling's formula)⁠이 $\binom{2n}{n} \approx 4^n/\sqrt{\pi n}$ 같은 어림을 줍니다.

이어지는 곳. 소수⁠(prime number)⁠ p에 대해 $\binom pk$($0 \lt k \lt p$)는 모두 p의 배수입니다. 분자 p!에는 p가 있지만 분모 k!(p−k)!에는 p보다 작은 수만 있기 때문입니다. 그래서 $(a+1)^p$를 전개하면 가운데 항이 모두 p의 배수⁠(multiple)⁠가 되어, p로 나눈 나머지⁠(remainder)⁠만 보면 $(a+1)^p$와 $a^p + 1$이 같습니다. 이것을 a = 1, 2, 3, …에 차례로 쓰면($a^p$의 나머지가 a와 같다면 $(a+1)^p$의 나머지는 $a^p + 1$, 곧 a + 1의 나머지와 같으므로) $a^p$를 p로 나눈 나머지가 a와 같다는 페르마 소정리⁠(Fermat's little theorem)⁠가 증명됩니다.

겹치는 집합들의 합집합⁠(union)⁠ 크기(집합의 크기⁠(cardinality)⁠)를 세는 포함배제 원리⁠(inclusion–exclusion principle)⁠에도 이항계수가 숨어 있습니다. 원소 하나가 집합 m개에 속해 있으면 그 원소는 '하나씩 더하기'에서 $\binom m1$번, '둘씩 겹친 것 빼기'에서 $\binom m2$번, … 세어지는데, 부호를 번갈아 붙인 합 $\binom m1 - \binom m2 + \binom m3 - \cdots$이 정확히 1이 되어 모든 원소가 한 번씩만 세어집니다.

격자 걸음은 다른 문제로도 이어집니다. →를 한 닢 따기, ↑를 한 닢 잃기로 읽고 돈이 0이나 목표 금액이 되는 순간 걸음을 멈추면 도박꾼의 파산⁠(gambler's ruin)⁠ 문제가 됩니다. 출발점과 끝점을 잇는 대각선 위로 한 번도 넘어가지 않는 길만 세면 $\frac{1}{n+1}\binom{2n}{n}$, 곧 카탈랑 수⁠(Catalan number)⁠가 나옵니다. 똑같은 사탕 n개를 아이 k명에게 나눠 주는 방법의 수는, 사탕(별) n개와 칸막이(막대) k−1개를 한 줄로 늘어놓고 막대가 놓일 자리를 고르는 이항계수 $\binom{n+k-1}{k-1}$로 셉니다(별과 막대⁠, stars and bars⁠).

격자 도시에서 오른쪽으로 k블록, 위로 n−k블록 가는 가장 짧은 길의 수가 이항계수입니다. 이 길들은 모양은 달라도 모두 길이가 n블록으로 같은데, 가로 거리와 세로 거리를 더한 이 길이가 두 지점 사이의 맨해튼 거리⁠(Manhattan distance)⁠입니다.

이항계수는 정보의 양과도 이어집니다. 동전을 n번 던져 앞면이 k번 나오는 순서의 수 $\binom nk$는, 지수만 보면 대략 $2^{nH(k/n)}$입니다. 여기서 $H(q) = -q\log_2 q - (1-q)\log_2(1-q)$는 앞면 확률이 q인 동전 한 번의 정보 엔트로피⁠(information entropy)⁠입니다. 예를 들어 1000번 중 100번 앞면인 순서는 $H(0.1) \approx 0.47$이라서 $2^{nH} \approx 2^{469}$이고, 정확히 세면 약 $2^{464}$가지입니다. 차이는 $\sqrt n$ 정도의 배수뿐이라 지수 469에 비하면 작습니다. 그 가운데 하나를 가리키는 데 약 464비트가 드는 셈입니다.