이항 계수¶

이항 계수 $\binom n k$는 서로 다른 $n$개의 원소에서 원소들의 배열 순서를 고려하지 않고 $k$개의 원소로 이루어진 집합을 선택하는 방법의 수(즉, 순서가 없는 집합의 개수)입니다.

이항 계수는 $(a + b) ^ n$을 전개했을 때 나타나는 계수이기도 합니다(이른바 이항 정리):

$$ (a+b)^n = \binom n 0 a^n + \binom n 1 a^{n-1} b + \binom n 2 a^{n-2} b^2 + \cdots + \binom n k a^{n-k} b^k + \cdots + \binom n n b^n $$

이 공식과 함께 계수를 효율적으로 계산할 수 있게 해 주는 삼각형은 17세기에 블레즈 파스칼이 발견한 것으로 알려져 있습니다. 그럼에도 이 공식은 13세기에 살았던 중국 수학자 양휘에게 이미 알려져 있었습니다. 어쩌면 페르시아 학자 오마르 하이얌이 발견했을 수도 있습니다. 게다가 그보다 앞선 기원전 3세기에 살았던 인도 수학자 핑갈라도 비슷한 결과를 얻었습니다. 뉴턴의 공로는 이 공식을 자연수가 아닌 지수에 대해서도 일반화했다는 점입니다.

계산¶

계산을 위한 해석적 공식:

$$ \binom n k = \frac {n!} {k!(n-k)!} $$

이 공식은 순서가 있는 배열 문제(서로 다른 $n$개의 원소에서 서로 다른 $k$개의 원소를 선택하는 방법의 수)로부터 쉽게 유도할 수 있습니다. 먼저 $k$개의 원소를 순서 있게 선택하는 방법의 수를 세어 봅시다. 첫 번째 원소를 선택하는 방법은 $n$가지, 두 번째 원소를 선택하는 방법은 $n-1$가지, 세 번째 원소를 선택하는 방법은 $n-2$가지이며, 이후도 마찬가지입니다. 그 결과 순서가 있는 배열의 수에 대한 공식을 얻습니다: $n (n-1) (n-2) \cdots (n - k + 1) = \frac {n!} {(n-k)!}$. 순서가 없는 각 배열은 정확히 $k!$개의 순서가 있는 배열에 대응한다는 점($k!$은 $k$개 원소의 가능한 순열의 수입니다)에 주목하면, 순서가 없는 배열로 쉽게 넘어갈 수 있습니다. $\frac {n!} {(n-k)!}$을 $k!$로 나누면 최종 공식을 얻습니다.

점화식(유명한 "파스칼의 삼각형"과 관련된 공식입니다):

$$ \binom n k = \binom {n-1} {k-1} + \binom {n-1} k $$

이는 해석적 공식을 이용하여 쉽게 유도할 수 있습니다.

$n \lt k$인 경우 $\binom n k$의 값은 0으로 간주한다는 점에 유의하십시오.

성질¶

이항 계수에는 다양한 성질이 많이 있습니다. 그중 가장 간단한 것들은 다음과 같습니다:

대칭 법칙:

$$ \binom n k = \binom n {n-k} $$
인수 넣기:

$$ \binom n k = \frac n k \binom {n-1} {k-1} $$
$k$에 대한 합:

$$ \sum_{k = 0}^n \binom n k = 2 ^ n $$
$n$에 대한 합:

$$ \sum_{m = 0}^n \binom m k = \binom {n + 1} {k + 1} $$
$n$과 $k$에 대한 합:

$$ \sum_{k = 0}^m \binom {n + k} k = \binom {n + m + 1} m $$
제곱의 합:

$$ {\binom n 0}^2 + {\binom n 1}^2 + \cdots + {\binom n n}^2 = \binom {2n} n $$
가중합:

$$ 1 \binom n 1 + 2 \binom n 2 + \cdots + n \binom n n = n 2^{n-1} $$
피보나치 수와의 관계:

$$ \binom n 0 + \binom {n-1} 1 + \cdots + \binom {n-k} k + \cdots + \binom 0 n = F_{n+1} $$

계산¶

해석적 공식을 이용한 직접 계산¶

첫 번째의 직접적인 공식은 코드로 작성하기가 매우 쉽지만, 이 방법은 비교적 작은 $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;
    return res;
}

개선된 구현¶

위 구현에서 분자와 분모는 같은 개수($k$)의 인수를 가지며, 각 인수는 1 이상이라는 점에 주목하십시오. 따라서 이 분수를 각각이 실숫값인 $k$개 분수의 곱으로 바꿀 수 있습니다. 그러나 현재 답에 다음 분수를 하나씩 곱해 나가는 각 단계 이후에도 답은 여전히 정수입니다(이는 인수분해의 성질에서 비롯됩니다).

C++ 구현:

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$에 대해 실행 속도가 느리다는 것입니다($\binom n k$를 계산하려면 모든 $\binom i j, 1 \le i \le n, 1 \le j \le n$의 표, 또는 적어도 $1 \le j \le \min (i, 2k)$까지의 표를 만들어야 하기 때문입니다). 시간 복잡도는 $\mathcal{O}(n^2)$라고 볼 수 있습니다.

C++ 구현:

const int maxn = ...;
int C[maxn + 1][maxn + 1];
C[0][0] = 1;
for (int n = 1; 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)$ 계산¶

마지막으로, 어떤 상황에서는 모든 팩토리얼을 미리 계산해 두어 이후 필요한 이항 계수를 나눗셈 두 번만으로 구하는 것이 유리합니다. 메모리가 부족해 파스칼의 삼각형 전체를 미리 계산할 수 없을 때 긴 연산을 사용한다면 이 방법이 유리할 수 있습니다.

$m$을 법으로 하는 이항 계수 계산¶

어떤 $m$을 법으로 이항 계수를 계산하는 문제를 꽤 자주 접하게 됩니다.

작은 $n$에 대한 이항 계수¶

앞서 설명한 파스칼의 삼각형 방법은 시간 복잡도 $\mathcal{O}(n^2)$가 필요하므로, 적당히 작은 $n$에 대해 $\binom{n}{k} \bmod m$의 모든 값을 계산하는 데 사용할 수 있습니다. 이 방법은 덧셈 연산만 사용하므로 어떤 법이든 처리할 수 있습니다.

큰 소수를 법으로 하는 이항 계수¶

이항 계수의 공식은 다음과 같습니다

$$\binom n k = \frac {n!} {k!(n-k)!},$$

따라서 어떤 소수 $m > n$을 법으로 이를 계산하려면 다음을 얻습니다

$$\binom n k \equiv n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \mod m.$$

먼저 $m$을 법으로 하는 모든 팩토리얼을 $\text{MAXN}!$까지 $O(\text{MAXN})$ 시간에 미리 계산합니다.

factorial[0] = 1;
for (int i = 1; i <= MAXN; i++) {
    factorial[i] = factorial[i - 1] * i % m;
}

그 후 이항 계수를 $O(\log m)$ 시간에 계산할 수 있습니다.

long long binomial_coefficient(int n, int k) {
    return factorial[n] * inverse(factorial[k] * factorial[n - k] % m) % m;
}

역원을 구하는 일반적인 방법으로 모든 팩토리얼의 역원을 $O(\text{MAXN} \log m)$에 미리 계산해 두면 이항 계수를 $O(1)$ 시간에 계산할 수도 있습니다. 합동식 $(x!)^{-1} \equiv ((x-1)!)^{-1} \cdot x^{-1}$와 $O(n)$에 모든 역원을 계산하는 방법을 사용하면 이 전처리를 $O(\text{MAXN})$ 시간에 끝낼 수도 있습니다.

long long binomial_coefficient(int n, int k) {
    return factorial[n] * inverse_factorial[k] % m * inverse_factorial[n - k] % m;
}

소수 거듭제곱을 법으로 하는 이항 계수¶

여기서는 어떤 소수 거듭제곱, 즉 어떤 소수 $p$에 대해 $m = p^b$를 법으로 하는 이항 계수를 계산하려고 합니다. $p > \max(k, n-k)$이면 앞 절에서 설명한 방법을 그대로 사용할 수 있습니다. 하지만 $p \le \max(k, n-k)$이면 $k!$와 $(n-k)!$ 중 적어도 하나는 $m$과 서로소가 아니므로 역원을 계산할 수 없습니다. 역원이 존재하지 않기 때문입니다. 그럼에도 이항 계수는 계산할 수 있습니다.

아이디어는 다음과 같습니다. 각 $x!$에 대해 $p^c$가 $x!$를 나누는, 즉 $p^c ~|~ x!$를 만족하는 가장 큰 지수 $c$를 계산합니다. 그 값을 $c(x)$라고 합시다. 그리고 $g(x) := \frac{x!}{p^{c(x)}}$라고 합시다. 그러면 이항 계수를 다음과 같이 쓸 수 있습니다.

$$\binom n k = \frac {g(n) p^{c(n)}} {g(k) p^{c(k)} g(n-k) p^{c(n-k)}} = \frac {g(n)} {g(k) g(n-k)}p^{c(n) - c(k) - c(n-k)}$$

흥미로운 점은 이제 $g(x)$가 소수 약수 $p$를 갖지 않는다는 것입니다. 따라서 $g(x)$는 m과 서로소이며, $g(k)$와 $g(n-k)$의 모듈러 역원을 계산할 수 있습니다.

$g$와 $c$의 모든 값을 미리 계산해 두면(동적 계획법을 사용해 $\mathcal{O}(n)$에 효율적으로 할 수 있습니다) 이항 계수를 $O(\log m)$ 시간에 계산할 수 있습니다. 또는 모든 역원과 $p$의 모든 거듭제곱을 미리 계산해 두고 이항 계수를 $O(1)$에 계산할 수도 있습니다.

$c(n) - c(k) - c(n-k) \ge b$이면 $p^b ~|~ p^{c(n) - c(k) - c(n-k)}$이므로 이항 계수가 $0$이 된다는 점에 유의하십시오.

임의의 수를 법으로 하는 이항 계수¶

이제 임의의 법 $m$에 대해 이항 계수를 계산합니다.

$m$의 소인수분해를 $m = p_1^{e_1} p_2^{e_2} \cdots p_h^{e_h}$라고 합시다. 모든 $i$에 대해 $p_i^{e_i}$를 법으로 하는 이항 계수를 계산할 수 있습니다. 이렇게 하면 서로 다른 합동식 $h$개를 얻습니다. 모든 법 $p_i^{e_i}$는 서로소이므로 중국인의 나머지 정리를 적용해 법들의 곱을 법으로 하는 이항 계수를 계산할 수 있으며, 이것이 바로 우리가 원하는 $m$을 법으로 하는 이항 계수입니다.

큰 $n$과 작은 법에 대한 이항 계수¶

$n$이 너무 크면 위에서 다룬 $\mathcal{O}(n)$ 알고리즘은 실용적이지 않습니다. 하지만 법 $m$이 작다면 여전히 $\binom{n}{k} \bmod m$을 계산하는 방법이 있습니다.

법 $m$이 소수일 때는 두 가지 선택지가 있습니다.

Lucas의 정리를 적용하면 $\binom{n}{k} \bmod m$을 계산하는 문제를 $x_i, y_i < m$인 $\binom{x_i}{y_i} \bmod m$ 꼴의 문제 $\log_m n$개로 나눌 수 있습니다. 나뉜 각 계수를 미리 계산한 팩토리얼과 팩토리얼의 역원으로 계산하면 복잡도는 $\mathcal{O}(m + \log_m n)$입니다.
P를 법으로 하는 팩토리얼을 계산하는 방법으로 필요한 $g$와 $c$ 값을 구한 뒤, 소수 거듭제곱을 법으로 하는 경우 절에서 설명한 대로 사용할 수 있습니다. 이 방법은 $\mathcal{O}(m \log_m n)$이 걸립니다.

$m$이 소수는 아니지만 제곱 인수가 없는 수라면, $m$의 소인수들을 구한 뒤 위의 두 방법 중 하나로 각 소인수를 법으로 하는 계수를 계산하고, 중국인의 나머지 정리로 최종 답을 구할 수 있습니다.

$m$에 제곱 인수가 있다면 Lucas의 정리 대신 소수 거듭제곱에 대한 Lucas의 정리의 일반화를 적용할 수 있습니다.