46. Combinatorics

조합론(Combinatorics)은 순열과 조합, 경우의 수 등을 다루는 분야이다. 조합론 문제를 풀기 위해서는 약간의 배경지식이 필요하다.

• 팩토리얼(계승, Factorial)은 $0$ 이상의 정수에 대해 정의되는 함수로 $0! = 1, \color{#0000FF}{n!} = (n-1)! \times n$이다. 팩토리얼을 실수 범위로 확장한 감마 함수(Gamma Function)라는 것도 존재하지만 웬만한 알고리즘 문제를 풀기 위해서는 팩토리얼만 알고 있어도 괜찮다.
• 순열(Permutation): 서로 다른 $n$개의 원소 중 $r$개를 중복 없이 골라서 순서대로 나열하는 경우의 수를 $\color{#0000FF}{_n\mathrm{P}_r}$ 또는 $\color{#0000FF}{\mathrm{P}(n, r)}$로 나타낸다.
• 조합(Combination): 서로 다른 $n$개의 원소 중 $r$개를 중복 없이 고르는 경우의 수를 $\color{#0000FF}{_n\mathrm{C}_r}$ 또는 ${\color{#0000FF}{\mathrm{C}(n, r)}}$로 나타낸다. 세계적으로는 $\color{#0000FF}{{n \choose r}}$을 많이 사용한다.
• 중복순열: 서로 다른 $n$개의 원소 중 $r$개를 중복을 허용하여 골라서 순서대로 나열하는 경우의 수를 $\color{#0000FF}{_n\mathrm{\Pi}_r}$로 나타내는 경우가 있으나 이 표현의 출처는 확실하지 않다.
• 중복조합: 서로 다른 $n$개의 원소 중 $r$개를 중복을 허용하여 고르는 경우의 수를 $\color{#0000FF}{_n\mathrm{H}_r}$로 표기한다.

그밖에 원순열, 같은 것이 있는 순열 등의 다른 경우도 존재하지만 여기서는 설명하지 않았다. 위에서 설명한 각각의 값들은 다음과 같이 계산할 수 있다.

$$_n\mathrm{P}_r=P(n,r)=\frac{n!}{(n-r)!}$$ $$_n\mathrm{C}_r=C(n,r)={n \choose r}=\frac{n!}{r!(n-r)!}$$ $$_n\mathrm{\Pi}_r=n^r$$ $$_n\mathrm{H}_r=_{n+r-1}\mathrm{C}_r=\frac{(n+r-1)!}{r!(n-1)!}$$

---

위에서 설명한 내용 중 조합론 문제를 풀 때 가장 많이 사용되는 것은 조합이며, 이와 관련하여 몇 가지 알아 두어야 할 개념들이 존재한다.

 

식 $(a+b)^n$을 전개했을 때, $a^rb^{n-r}$의 계수는 $r$개의 $a$와 $(n-r)$개의 $b$를 순서대로 나열하는 경우의 수와 같다. 나열하는 문자의 전체 개수가 $n$이므로 이 값은 다음과 같다:

$$\frac{n!}{r!(n-r)!}$$

이것은 $_n\mathrm{C}_r$의 정의와 같다. 즉 $a^rb^{n-r}$의 계수는 $_n\mathrm{C}_r$과 같음을 알 수 있다. 이것을 이항정리(Binomial Theorem)라고 하고, $a^rb^{n-r}$의 계수들을 이항계수(Binomial Coefficient)라고 한다.

 

$n$과 $r$이 작은 경우의 이항계수는 파스칼의 삼각형을 이용하여 구할 수 있다. 파스칼의 삼각형으로부터 다음과 같은 항등식을 유도할 수 있으며, 이를 파스칼 항등식이라고 한다.

$${n \choose r}={n-1 \choose r-1}+{n-1 \choose r}$$

코드로 구현하기도 쉬운 형태이다.

b[0][0] = 1;
for(int i = 1; i <= n; i++)
{
    b[i][0] = i;
    for(int j = 1; j <= i; j++)a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
}

단 이 코드는 $n$이 $68$ 이상이 되면 부호 없는 $8$바이트 정수 자료형을 사용해도 일부 값을 계산하는 과정에서 오버플로우가 발생하게 된다. 따라서 $n$과 $r$의 제한이 더 큰 문제들의 경우 이항계수를 소수 $p$로 나눈 나머지를 대신 사용하게 된다.

 

$n$의 최대값이 $5000$ 이하인 경우 $2$차원 배열을 이용하여 이항계수를 저장하는 방법을 사용할 수 있지만, $n$이 $1$만 이상이 될 수 있을 경우 메모리 제한으로 인해 $2$차원 배열을 선언하기 어려워진다. 따라서 $1$차원 배열을 이용하여 이항 계수를 구해야 한다. 배열에 이항 계수를 직접 저장하지 않고 각각의 팩토리얼 값을 저장한다면 이항 계수는 두 번의 나눗셈 또는 모듈러 연산을 이용하여 구할 수 있다.

f[0] = 1;
for(int i = 1; i <= n; i++)f[i] = i * f[i - 1] % p;

이렇게 전처리하면 $_n\mathrm{P}_r$, $_n\mathrm{C}_r$의 값은 다음과 같이 구할 수 있다. modinv 함수는 이전 글에 나온 것과 동일하다.

nPr = modinv(f[n], f[r])
nCr = modinv(f[n], f[r] * f[n - r] % p)

$n$이 $10$만~$100$만 단위까지 커질 수 있는 문제의 경우 대부분 이 방법으로 이항계수를 구하게 된다.

---

아주 드물게 나오는 유형으로 $(a+b)^n$또는 $(a-b)^n$에서 $a$의 지수가 짝수인 항들의 합 또는 홀수인 항들의 합을 구해야 하는 경우가 있다. $n$이 크다면 각각의 항들의 값을 하나씩 구하는 것은 너무 느리다. 이때 두 식을 각각 전개하면,

$$(a+b)^n=_n\text{C}_0a^nb^0+_n\text{C}_1a^{n-1}b^1+\ldots+_n\text{C}_na^0b^n$$

$$(a-b)^n=_n\text{C}_0a^nb^0-_n\text{C}_1a^{n-1}b^1+\ldots_n\text{C}_na^0b^n$$

첫 번째 식과 두 번째 식을 더하면 $a$의 지수가 홀수인 항이 모두 사라진다. 첫 번째 식에서 두 번째 식을 빼면 $a$의 지수가 짝수인 항이 모두 사라진다. 즉, 다음과 같은 식을 유도할 수 있다.

$$_n\text{C}_0a^nb^0+_n\text{C}_2a^{n-2}b^2+_n\text{C}_4a^{n-4}b^4+\ldots=\frac{(a+b)^n+(a-b)^n}{2}$$

$$_n\text{C}_1a^{n-1}b^1+_n\text{C}_3a^{n-3}b^3+_n\text{C}_5a^{n-5}b^5+\ldots=\frac{(a+b)^n-(a-b)^n}{2}$$

따라서 항들의 값을 하나씩 구하지 않고도 답을 구할 수 있다.

---

[연습문제]

 

BOJ 11051. 이항 계수 2 (Silver I)

$n$이 $1000$ 이하이므로 $2$차원 배열에 이항 계수를 저장하면 풀 수 있다.

 

BOJ 11401. 이항 계수 3 (Gold I)

$n$이 $400$만 이하이므로 $1$차원 배열을 사용해야 한다. 위에서 설명한 방법대로 구현하면 된다.

 

BOJ 13977. 이항 계수와 쿼리 (Gold I)

11401번의 쿼리형 버전이다. 풀이는 거의 똑같다.

 

BOJ 18709. Flipping El-fetiera (Platinum IV)

지수가 홀수인 항과 짝수인 항의 합을 구하는 방법을 사용해야 하는 첫 번째 문제이다.

 

CF 1444B. Divide and Sum (1900)

$2n$개의 원소를 오름차순으로 정렬하고 차례로 $p$의 맨 앞 또는 $q$의 맨 뒤부터 채워 넣는 경우를 생각하면 $f(p, q) = ($큰 $n$개의 원소의 합$) - ($작은 $n$개의 원소의 합$)$이 항상 성립한다. 배열 $p$의 가짓수는 $2n$개의 원소 중 $n$개를 선택하는 경우의 수와 같으므로 $_{2n}\mathrm{C}_n$이다. 조합을 구하면 문제를 해결할 수 있다.

 

CF 1332E. Height All the Same (2100)

지수가 홀수인 항과 짝수인 항의 합을 구하는 방법을 사용해야 하는 두 번째 문제이다. $n$과 $m$이 모두 홀수인 경우 항상 모든 칸의 높이를 같게 할 수 있으므로 $(R-L+1)^{nm}$이 답이고, 그렇지 않은 경우 처음 상태에서 높이가 홀수인 칸과 짝수인 칸의 개수가 모두 짝수여야 하므로 위에서 나온 공식을 이용해서 문제를 풀 수 있다.

 

→ solved.ac tag: combinatorics