조합론 (Combinatorics)

정의

조합론 (Combinatorics) 은 유한 집합의 원소를 세는 수학 분야. PS 에서는 주로 순열 (Permutation), 조합 (Combination), 이항계수 (Binomial Coefficient) 계산과 mod 연산을 다룬다.

핵심 연산:

• nPr (순열): n 개 중 r 개를 순서를 고려해 뽑기 = n! / (n-r)!
• nCr (조합): n 개 중 r 개를 순서 무관 뽑기 = n! / (r! · (n-r)!)
• 이항계수: C(n, r) = nCr, Pascal 의 삼각형 C(n, r) = C(n-1, r-1) + C(n-1, r)

17세기 Blaise Pascal, Pierre de Fermat 등이 확률론과 함께 발전. PS 에서는 DP, mod 1e9+7, Lucas 정리, Catalan 수 등으로 확장.

문제 상황과 동기

경우의 수 세기:

• “N 명 중 K 명을 뽑는 방법?” → nCr
• “길이 N 순열의 개수?” → N!
• “중복 조합?” → (n+r-1)Cr

naive 계산의 한계:

• nCr = n! / (r! · (n-r)!) 직접 계산: N ≥ 21 이면 팩토리얼 오버플로우.
• mod p 연산: (a / b) mod p 는 정의 안 됨 → 역원 필요.
• Q 번 쿼리: 매번 팩토리얼 계산하면 O(N · Q) → O(N + Q) 로.

핵심 통찰:

1. 전처리 + 역원: fact[n], inv_fact[n] 을 O(N) 에 미리 계산 → nCr mod p O(1) 쿼리.
2. Pascal 의 삼각형 DP: C[n][r] = C[n-1][r-1] + C[n-1][r] → O(N²) 전처리, mod 연산 깔끔.
3. Lucas 정리: mod p (p 소수, 작은 p) 일 때 O(p² log_p N) 계산.

시각화

핵심 아이디어

1. 순열 (nPr)

n 개 중 r 개를 순서를 고려해 뽑기.

nPr = n · (n-1) · ... · (n-r+1) = n! / (n-r)!

2. 조합 (nCr)

n 개 중 r 개를 순서 무관 뽑기. 순열에서 r! 로 나눔 (중복 제거).

nCr = n! / (r! · (n-r)!)

대칭성: C(n, r) = C(n, n-r).

3. Pascal 의 삼각형

C(n, r) = C(n-1, r-1) + C(n-1, r)

base: C(n, 0) = C(n, n) = 1.

invariant: 이항정리 (1 + x)^n = Σ C(n, r) x^r.

4. mod p 계산 (p 소수)

Fermat 의 소정리 또는 확장 유클리드로 역원 구하기.

nCr_mod_p = fact[n] * inv_fact[r] % p * inv_fact[n-r] % p

알고리즘

팩토리얼 + 역원 전처리 (mod p)

precompute(N, p):
    fact[0] = 1
    for i = 1..N:
        fact[i] = fact[i-1] * i % p
    inv_fact[N] = inv(fact[N], p)   # Fermat or exgcd
    for i = N-1..0:
        inv_fact[i] = inv_fact[i+1] * (i+1) % p

nCr_mod(n, r, p):
    if r < 0 or r > n: return 0
    return fact[n] * inv_fact[r] % p * inv_fact[n-r] % p

Pascal 의 삼각형 DP

build_pascal(N):
    C[0][0] = 1
    for n = 1..N:
        C[n][0] = 1
        for r = 1..n:
            C[n][r] = C[n-1][r-1] + C[n-1][r]

구현

// nCr mod p (팩토리얼 + 역원 전처리)
#include <bits/stdc++.h>
using namespace std;
​
const int MAXN = 1000005;
const long long MOD = 1000000007;
​
long long fact[MAXN], inv_fact[MAXN];
​
long long pow_mod(long long a, long long n, long long m) {
  long long r = 1;
  a %= m;
  while (n > 0) {
      if (n & 1) r = r * a % m;
      a = a * a % m;
      n >>= 1;
  }
  return r;
}
​
void precompute(int n, long long p) {
  fact[0] = 1;
  for (int i = 1; i <= n; i++)
      fact[i] = fact[i-1] * i % p;
  inv_fact[n] = pow_mod(fact[n], p - 2, p);
  for (int i = n - 1; i >= 0; i--)
      inv_fact[i] = inv_fact[i+1] * (i+1) % p;
}
​
long long nCr(int n, int r) {
  if (r < 0 || r > n) return 0;
  return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}
​
int main() {
  int n, r;
  cin >> n >> r;
  precompute(n, MOD);
  cout << nCr(n, r) << "\n";
  return 0;
}

# nCr mod p (팩토리얼 + 역원)
MOD = 10**9 + 7
MAXN = 10**6
​
fact = [1] * (MAXN + 1)
inv_fact = [1] * (MAXN + 1)
​
def precompute(n, p):
  for i in range(1, n + 1):
      fact[i] = fact[i-1] * i % p
  inv_fact[n] = pow(fact[n], p - 2, p)
  for i in range(n - 1, -1, -1):
      inv_fact[i] = inv_fact[i+1] * (i+1) % p
​
def nCr(n, r):
  if r < 0 or r > n:
      return 0
  return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD
​
n, r = map(int, input().split())
precompute(n, MOD)
print(nCr(n, r))

// Pascal 의 삼각형 DP (작은 N ≤ 1000)
import java.util.*;
public class Main {
  static long[][] C;
  static long MOD = 1000000007;
  
  static void buildPascal(int n) {
      C = new long[n+1][n+1];
      for (int i = 0; i <= n; i++) {
          C[i][0] = 1;
          for (int j = 1; j <= i; j++)
              C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
      }
  }
  
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(), r = sc.nextInt();
      buildPascal(n);
      System.out.println(C[n][r]);
  }
}

5 2

10

1000 500

159835829

복잡도

응용

1. 이항정리

(x + y)^n = Σ (r=0 to n) C(n, r) x^(n-r) y^r

2. 중복 조합

n 가지에서 r 개를 중복 허용 뽑기 (순서 무관):

H(n, r) = C(n + r - 1, r)

3. Catalan 수

Cat(n) = C(2n, n) / (n + 1) = C(2n, n) - C(2n, n+1)

올바른 괄호 문자열, BST 개수, 산 모양 경로 등.

4. 포함-배제 원리

|A ∪ B| = |A| + |B| - |A ∩ B|

일반화: |A₁ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + ...

5. Stirling 수

• 제1종: 순열을 cycle 로 분해
• 제2종: n 개 원소를 k 개 비어있지 않은 부분집합으로

함정

1. 팩토리얼 오버플로우

n! 은 n ≥ 21 이면 long long 넘음. mod 연산 또는 큰 수 라이브러리.

2. 역원 존재 조건

mod p 가 소수가 아니면 Fermat 불가. 확장 유클리드 또는 Lucas (p 소수 분해).

3. nCr = 0 케이스

r > n 또는 r < 0 일 때 0. 경계 체크 누락하면 WA.

4. mod 연산 순서

(a / b) % p (X) → a * inv(b, p) % p (O).

5. 중복 조합 실수

“중복 허용 조합” 은 C(n, r) 이 아니라 C(n+r-1, r).

변형

BOJ 연습 문제

참고

• 모듈러 역원
• Pascal 의 삼각형
• Lucas 정리
• Catalan 수