이항 계수 C_n^k는 서로 다른 n개의 물건에서 원소의 배치 순서를 고려하지 않고 k개의 물건으로 이루어진 집합을 고르는 방법의 수(즉, 순서가 없는 집합의 수)를 말합니다.
또한 이항 계수는 (a+b)^n의 전개식(이른바 뉴턴의 이항 정리)에 나타나는 계수입니다:
(a+b)^n = C_n^0 a^n + C_n^1 a^{n-1} b + C_n^2 a^{[…]
이 공식은 계수를 효율적으로 구할 수 있게 해 주는 삼각형과 마찬가지로 17세기에 살았던 블레즈 파스칼(Blaise Pascal)이 발견한 것으로 여겨집니다. 그럼에도 불구하고, 이 공식은 이미 13세기에 살았던 중국의 수학자 양휘(Yang Hui)에게도 알려져 있었습니다. 어쩌면 페르시아의 학자 오마르 하이얌(Omar Khayyam)이 이 공식을 발견했을 수도 있습니다. 더 나아가, 이미 기원전 3세기에 살았던 인도의 수학자 핑갈라(Pingala)도 이와 비슷한 결과를 얻었습니다. 뉴턴의 공로는 이 공식을 자연수가 아닌 거듭제곱으로 일반화했다는 데 있습니다.
계산 계산을 위한 해석적 공식은 다음과 같습니다:
C_n^k = \frac{n!}{k! (n-k)!}
이 공식은 비순서 선택 문제(n개의 원소에서 k개의 원소를 순서 없이 선택하는 방법의 수)로부터 쉽게 유도할 수 있습니다. 먼저 순서 있는 선택의 수를 세어 봅시다. 첫 번째 원소를 선택하는 방법은 n가지, 두 번째는 n-1가지, 세 번째는 n-2가지이며, 이후도 마찬가지입니다. 그 결과 순서 있는 선택의 수에 대해 다음 공식을 얻습니다: n (n-1) (n-2) \ldots (n-k+1) = \frac{n!}{(n-k)!} . 각각의 비순서 선택에 정확히 k!개의 순서 있는 선택이 대응한다는 점(이는 k개 원소의 가능한 모든 순열의 수이기 때문입니다)에 주목하면 비순서 선택으로 쉽게 넘어갈 수 있습니다. 그 결과 \frac{n!}{(n-k)!}를 k!로 나누면 구하려는 공식을 얻습니다.
점화식(유명한 “파스칼의 삼각형"과 관련된 식)은 다음과 같습니다:
C_n^k = C_{n-1}^{k-1} + C_{n-1}^k
이는 앞의 공식으로부터 쉽게 유도할 수 있습니다.
특별히 주목할 점은, n<k일 때 C_n^k의 값은 항상 0으로 간주한다는 것입니다.
성질 이항 계수는 다양한 성질을 많이 가지고 있으며, 그중 가장 간단한 것들을 소개합니다:
대칭 법칙: C_n^k = C_n^{n-k}
인수 넣기-빼기: C_n^k = \frac{n}{k} C_{n-1}^{k-1}
k에 대한 합: \sum_{k=0}^n C_n^k = 2^n
n에 대한 합: \sum_{m=0}^n C_m^k = C_{n+1}^{k+1}
n과 k에 대한 합: \sum_{k=0}^{m} C_{n+k}^k = C_{n+m+1}^m
제곱의 합: (C_n^0)^2 + (C_n^1)^2 + \ldots + (C_n^n)^2 = C_{2[…]
가중 합: 1 C_n^1 + 2 C_n^2 + \ldots + n C_n^n = n 2^{n-1}
피보나치 수와의 관계: C_n^0 + C_{n-1}^1 + \ldots + C_{n-k}^k + \ldots +[…]
프로그램에서의 계산 해석적 공식에 의한 직접 계산 첫 번째 공식, 즉 직접적인 공식에 따른 계산은 프로그래밍하기가 매우 쉽지만, 이 방법은 n과 k가 비교적 작은 값일 때에도 오버플로가 발생하기 쉽습니다(답이 어떤 자료형에 충분히 들어가는 경우에도, 중간 단계의 팩토리얼을 계산하는 과정에서 오버플로가 발생할 수 있습니다). 따라서 이 방법은 [[Длинная арифметика|긴 산술]]과 함께 사용해야만 하는 경우가 매우 많습니다:
int C (int n, int k) { int res = 1; for (int i=n-k+1; i<=n; ++i) res *= i; for (int i=2; i<=k; ++i) res /= i; } 개선된 구현 위의 구현에서 분자와 분모에는 같은 개수(k)의 인수가 있으며, 각 인수는 1 이상임을 알 수 있습니다. 따라서 우리의 분수를 각각 실숫값을 갖는 k개의 분수의 곱으로 바꿀 수 있습니다. 그러나 현재 답에 각각의 다음 분수를 곱한 후에도 여전히 정수가 얻어진다는 것을 알 수 있습니다(이는 예를 들어 “넣기-빼기” 성질에서 따라 나옵니다). 따라서 다음과 같은 구현을 얻습니다:
int C (int n, int k) { double res = 1; for (int i=1; i<=k; ++i) res = res * (n-k+i) / i; return (int) (res + 0.01); } 여기서는 누적되는 오차 때문에 실수 값이 실제 값보다 약간 작아질 수 있다는 점(예를 들어 3 대신 2.99999)을 고려하여, 실수를 정수로 신중하게 변환합니다.
파스칼의 삼각형 점화식을 이용하면 이항 계수의 표(사실상 파스칼의 삼각형)를 만들고, 그 표에서 결과를 가져올 수 있습니다. 이 방법의 장점은 중간 결과가 결코 답을 넘지 않으며, 표의 새로운 원소를 하나 계산할 때마다 덧셈이 단 한 번만 필요하다는 것입니다. 단점은 실제로는 표 전체가 필요하지 않고 단 하나의 값만 필요한 경우에 N과 K가 크면 느리게 동작한다는 것입니다(C_n^k를 계산하려면 모든 C_i^j,\ \ 1 \le i \le n,\ \ 1 \le j \le n에 대한 표를, 또는 적어도 1 \le j \le \min(i,2k)까지의 표를 만들어야 하기 때문입니다).
const int maxn = …; int C[maxn+1][maxn+1]; for (int n=0; n<=maxn; ++n) { C[n][0] = C[n][n] = 1; for (int k=1; k<n; ++k) C[n][k] = C[n-1][k-1] + C[n-1][k]; } 값의 표 전체가 필요하지 않다면, 쉽게 알 수 있듯이 표에서 두 행(현재 행인 n번째 행과 이전 행인 n-1번째 행)만 저장하면 충분합니다.
O(1)로 계산하기 마지막으로, 어떤 상황에서는 모든 팩토리얼의 값을 미리 계산해 두는 것이 유리한데, 그렇게 하면 이후에 필요한 이항 계수를 나눗셈 두 번만으로 구할 수 있기 때문입니다. 이는 긴 산술(Long arithmetic)을 사용할 때 메모리가 부족하여 파스칼의 삼각형 전체를 미리 계산할 수 없는 경우나, 어떤 소수 모듈로에 대해 계산해야 하는 경우에 유리할 수 있습니다(모듈로가 소수가 아니면 분수의 분자를 분모로 나눌 때 어려움이 생기는데, 모듈로를 소인수분해하고 모든 수를 그 소수들의 거듭제곱으로 이루어진 벡터 형태로 저장하면 이 어려움을 극복할 수 있습니다. “소인수분해된 형태의 긴 산술” 절을 참고하십시오).