조합론 (Combinatorics)

교란(완전순열)이란 어떤 원소도 원래 자리에 오지 않는 순열입니다. $n$개 원소의 교란수 $D_n$을 포함-배제 원리로 유도합니다.

$A_i$를 "$i$번째 원소가 제자리에 있는 순열의 집합"이라 하면:

• $|A_i| = (n-1)!$
• $|A_i \cap A_j| = (n-2)!$
• 일반적으로 $|A_{i_1} \cap \cdots \cap A_{i_k}| = (n-k)!$

적어도 하나의 원소가 제자리에 있는 순열의 수는:

따라서 교란수는:

처음 몇 개의 값: $D_1 = 0,\; D_2 = 1,\; D_3 = 2,\; D_4 = 9,\; D_5 = 44,\; D_6 = 265$

점화식: $D_n = (n-1)(D_{n-1} + D_{n-2})$, 그리고 $D_n = nD_{n-1} + (-1)^n$

오일러 피 함수와의 관계

오일러 피 함수 $\phi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 것의 개수입니다. 이것도 포함-배제 원리로 유도됩니다.

$n$의 소인수가 $p_1, p_2, \ldots, p_k$일 때, $A_i$를 "$1$부터 $n$까지 중 $p_i$의 배수의 집합"이라 하면:

예시: $\phi(60) = 60 \cdot \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right) = 60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16$

생성함수

생성함수(Generating Function)는 수열 $\{a_n\}$을 멱급수의 계수로 인코딩한 것입니다.

보통 생성함수 (OGF)

대표적인 생성함수

생성함수의 연산

지수 생성함수 (EGF)

수열 $\{a_n\}$의 지수 생성함수는 다음과 같이 정의됩니다.

지수 생성함수는 라벨이 붙은(labeled) 구조를 셀 때 특히 유용합니다. 두 EGF의 곱은 라벨 집합의 분할에 대응합니다.

점화식 풀이 예시: 피보나치 수열

$F_0 = 0, \; F_1 = 1, \; F_n = F_{n-1} + F_{n-2}$의 닫힌 형태를 생성함수로 구합니다.

풀이: $F(x) = \sum_{n=0}^{\infty} F_n x^n$으로 놓으면, 점화식에 $x^n$을 곱하고 $n \ge 2$에서 합하면:

부분분수 분해하면 ($\alpha = \frac{1+\sqrt{5}}{2}$, $\beta = \frac{1-\sqrt{5}}{2}$일 때):

따라서 비네 공식(Binet's formula)을 얻습니다:

점화식 풀이 예시: 하노이 탑

$T_n = 2T_{n-1} + 1$, $T_1 = 1$일 때 생성함수를 이용한 풀이:

$T(x) = \sum_{n=1}^{\infty} T_n x^n$으로 놓으면:

따라서 $T_n = 2^n - 1$을 얻습니다.

카탈란 수

카탈란 수(Catalan Number) $C_n$은 조합론에서 자주 등장하는 수열입니다.

처음 몇 개의 값

카탈란 수가 나타나는 문제

• $n$쌍의 올바른 괄호 배열의 수
• $n+1$개의 잎을 가진 이진 트리(full binary tree)의 수
• 볼록 $(n+2)$각형의 삼각분할 수
• $n \times n$ 격자에서 대각선을 넘지 않는 단조 경로의 수
• $n+1$개의 행렬을 곱하는 순서의 수 (행렬 연쇄 곱셈)
• $n$개의 노드를 가진 서로 다른 이진 탐색 트리의 수
• 스택 정렬 가능한 순열의 수

점화식

또는 닫힌 형태의 점화식:

생성함수 유도

$C(x) = \sum_{n=0}^{\infty} C_n x^n$으로 놓으면, 점화식 $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$는 합성곱이므로:

이차방정식의 근의 공식을 적용하면:

$C(0) = C_0 = 1$이어야 하므로 ($+$를 택하면 $x \to 0$에서 발산), $-$부호를 택합니다:

여기서 $\sqrt{1 - 4x} = \sum_{n=0}^{\infty} \binom{1/2}{n}(-4x)^n$을 일반화된 이항정리로 전개하면 $C_n = \frac{1}{n+1}\binom{2n}{n}$을 복원할 수 있습니다.

스털링 수

스털링 수(Stirling Number)는 순열과 분할을 세는 데 사용되는 중요한 수입니다.

제1종 스털링 수 (부호 없는): $\left[\begin{smallmatrix}n\\k\end{smallmatrix}\right]$

$n$개의 원소를 $k$개의 순환(사이클)으로 분할하는 경우의 수입니다. $c(n,k)$ 또는 $\left|s(n,k)\right|$로도 표기합니다.

점화식:

해석: $n$번째 원소를 기존 $(n-1)$개 중 하나의 사이클에 삽입 ($(n-1)$가지)하거나, 단독 사이클을 형성합니다.

제1종 스털링 수 표

제2종 스털링 수: $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$

$n$개의 원소를 $k$개의 공집합이 아닌 부분집합으로 분할하는 경우의 수입니다. $S(n,k)$로도 표기합니다.

점화식:

해석: $n$번째 원소를 기존 $k$개 블록 중 하나에 넣거나 ($k$가지), 단독 블록을 만듭니다.

명시적 공식 (포함-배제):

제2종 스털링 수 표

스털링 수와 거듭제곱의 관계

일반 거듭제곱을 하강 계승으로 변환:

이 관계는 $\sum_{k=1}^{n} k^m$ 같은 거듭제곱 합을 계산하는 데 활용됩니다.

벨 수 (Bell Number)

$n$개의 원소를 임의의 개수의 비어있지 않은 부분집합으로 분할하는 총 경우의 수를 벨 수 $B_n$이라 합니다.

처음 몇 개의 값: $B_0=1, \; B_1=1, \; B_2=2, \; B_3=5, \; B_4=15, \; B_5=52, \; B_6=203$

뫼비우스 반전 공식

뫼비우스 반전 공식(Mobius Inversion Formula)은 정수론과 조합론을 잇는 중요한 도구입니다.

뫼비우스 함수

뫼비우스 함수 $\mu(n)$은 다음과 같이 정의됩니다.

처음 몇 개의 값:

핵심 성질

뫼비우스 반전 공식

$f(n) = \sum_{d \mid n} g(d)$이면 다음이 성립합니다:

응용: 오일러 피 함수

$\sum_{d \mid n} \phi(d) = n$이므로, 뫼비우스 반전을 적용하면:

응용: 목걸이 문제 (번사이드 보조정리와의 연결)

$k$가지 색으로 길이 $n$인 원형 목걸이를 만드는 서로 다른 방법의 수:

여기서 $\phi$는 오일러 피 함수입니다. 이 공식은 번사이드 보조정리(Burnside's lemma)에서도 유도됩니다.

램지 이론

램지 이론(Ramsey Theory)은 "충분히 큰 구조 안에는 반드시 규칙적인 부분 구조가 존재한다"는 것을 다루는 조합론의 분야입니다.

램지 수의 정의

램지 수 $R(s,t)$는 다음을 만족하는 최소의 양의 정수 $n$입니다:

$K_n$ (완전그래프)의 각 변을 빨강 또는 파랑으로 색칠하면, 반드시 빨간 $K_s$ 또는 파란 $K_t$가 존재한다.

간단한 경우

• $R(s, 1) = 1$, $R(s, 2) = s$ (모든 $s \ge 1$)
• $R(3, 3) = 6$: 6명의 모임에서 서로 아는 3명 또는 서로 모르는 3명이 반드시 존재

$R(3,3) = 6$의 증명

$R(3,3) \le 6$ 증명: 6명 중 한 사람 $v$를 택하면, 비둘기집 원리에 의해 나머지 5명 중 적어도 3명은 $v$와 같은 관계(모두 아는 사이이거나 모두 모르는 사이)입니다. 이 3명을 $a, b, c$라 하자.

• $v$가 $a, b, c$를 모두 안다면: $a, b, c$ 중 둘이라도 서로 알면 아는 3명이 존재. 셋 다 서로 모르면 모르는 3명이 존재.
• $v$가 $a, b, c$를 모두 모른다면: 동일한 논리 적용.

$R(3,3) > 5$ 증명: $K_5$의 변을 정오각형의 변은 빨강, 대각선은 파랑으로 칠하면, 단색 삼각형이 존재하지 않습니다.

알려진 램지 수

램지 수의 상한 (에르되시-세케레시)

특히 $R(s,s) \le \binom{2s-2}{s-1} \le 4^{s-1}$입니다.

추가 항등식 및 공식

하키 스틱 항등식 (Hockey Stick Identity)

파스칼 삼각형에서 대각선 방향으로 연속된 이항계수의 합이 하나의 이항계수로 표현됩니다.

이항계수 역수의 합

뤼카 정리 (Lucas' Theorem)

소수 $p$에 대해, $n = \sum n_i p^i$, $k = \sum k_i p^i$ ($p$진 전개)일 때:

쿠머 정리 (Kummer's Theorem)

$\binom{m+n}{m}$에서 소수 $p$의 지수(정확한 거듭제곱)는 $m$과 $n$을 $p$진법으로 더할 때 발생하는 올림(carry)의 횟수와 같습니다.

세기 문제: 다양한 풀이 비교

같은 조합론 문제를 서로 다른 방법으로 풀면 깊은 통찰을 얻을 수 있습니다. 아래에서 하나의 문제를 네 가지 방법으로 풀어 보겠습니다.

문제: $n$개의 서로 다른 공을 $k$개의 서로 다른 상자에 넣되, 빈 상자가 없도록 하는 방법의 수

이 수를 전사함수(surjection)의 수라 하며, $k! \left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$와 같습니다 (제2종 스털링 수와 관련).

풀이 1: 직접 세기 (Direct Counting)

제한 없이 넣는 총 방법의 수는 $k^n$입니다. 여기서 "빈 상자가 있는 경우"를 빼야 합니다. 하지만 직접 세기로는 겹치는 부분 때문에 포함-배제가 필요합니다.

풀이 2: 포함-배제 원리

$A_i$를 "$i$번째 상자가 비어 있는 배치의 집합"이라 합시다.

• $|A_i| = (k-1)^n$ (한 상자 제외)
• $|A_i \cap A_j| = (k-2)^n$ (두 상자 제외)
• 일반적으로 $|A_{i_1} \cap \cdots \cap A_{i_m}| = (k-m)^n$

전사함수의 수는:

풀이 3: 생성함수

각 상자에 적어도 1개의 공이 들어가야 하므로, 각 상자의 지수 생성함수는 $e^x - 1$입니다. $k$개의 상자가 구별되므로:

$x^n/n!$의 계수에 $n!$을 곱하면 위의 포함-배제 공식과 동일한 결과를 얻습니다.

풀이 4: 제2종 스털링 수 이용

먼저 $n$개의 공을 $k$개의 비어있지 않은 블록으로 분할하는 방법 $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$을 구하고, 각 블록을 $k$개의 상자에 대응시키면:

이항계수 항등식: 증명 방법 비교

같은 이항계수 항등식을 여러 가지 방법으로 증명할 수 있습니다. 각 방법의 장단점을 비교합니다.

반더몬드 항등식: $\displaystyle\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}$

증명 1: 조합적 증명 (Combinatorial Proof)

$m$명의 남학생과 $n$명의 여학생 중 $r$명의 위원을 뽑는 상황을 생각합니다. 좌변은 전체 $(m+n)$명에서 $r$명을 뽑는 방법의 수입니다. 우변은 남학생에서 $k$명, 여학생에서 $r-k$명을 뽑는 모든 경우를 합한 것입니다. 같은 것을 세고 있으므로 두 식은 같습니다.

증명 2: 대수적 증명 (Algebraic Proof)

$(1+x)^m(1+x)^n = (1+x)^{m+n}$에서 $x^r$의 계수를 비교합니다.

• 좌변에서 $x^r$의 계수: $(1+x)^m$에서 $x^k$의 계수 $\binom{m}{k}$와 $(1+x)^n$에서 $x^{r-k}$의 계수 $\binom{n}{r-k}$의 합성곱 → $\sum_{k}\binom{m}{k}\binom{n}{r-k}$
• 우변에서 $x^r$의 계수: $\binom{m+n}{r}$

증명 3: 생성함수 증명

$(1+x)^m$과 $(1+x)^n$의 곱이 $(1+x)^{m+n}$이라는 사실 자체가 생성함수의 합성곱 정리입니다. 증명 2와 본질적으로 같지만, 생성함수의 관점에서는 수열의 합성곱이라는 구조를 명시적으로 활용합니다.

추 항등식 (Chu–Vandermonde): $\displaystyle\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$

음의 상단 지수를 가진 이항계수를 양수로 변환하는 공식입니다. 이를 반더몬드 항등식에 적용하면 상부 부호 반전(upper negation)이라 불리는 유용한 변환을 얻습니다.

이중 세기 (Double Counting)의 다른 예

항등식: $\displaystyle k\binom{n}{k} = n\binom{n-1}{k-1}$

조합적 증명: $n$명 중 $k$명의 위원회를 뽑고 위원장 1명을 선출하는 방법을 두 가지로 셉니다.

• 위원회를 먼저 뽑고($\binom{n}{k}$), 그 중 위원장 선출($k$): 좌변
• 위원장을 먼저 뽑고($n$), 나머지 $k-1$명을 뽑음($\binom{n-1}{k-1}$): 우변

카탈란 수: 다양한 유도 방법

카탈란 수 $C_n = \frac{1}{n+1}\binom{2n}{n}$은 여러 방법으로 유도할 수 있습니다. 이미 위에서 생성함수를 이용한 유도를 보았으므로, 여기서는 다른 방법들을 소개합니다.

유도 1: 재귀 관계로부터

$n$쌍의 올바른 괄호 배열을 생각합니다. 첫 번째 여는 괄호 '('에 대응하는 닫는 괄호 ')'의 위치가 $2k+2$번째라 하면 ($k = 0, 1, \ldots, n-1$):

• 첫 괄호 쌍 안에 $k$쌍의 올바른 괄호: $C_k$가지
• 첫 괄호 쌍 바깥에 $n-1-k$쌍의 올바른 괄호: $C_{n-1-k}$가지

유도 2: 반사 원리 (André의 방법)

$n \times n$ 격자에서 $(0,0)$에서 $(n,n)$까지 오른쪽(R) 또는 위쪽(U)으로만 이동하되, 대각선 $y = x$ 위로(즉, $y > x$가 되도록) 올라가지 않는 경로의 수가 $C_n$입니다.

전체 경로 수: R과 U를 각각 $n$번씩 사용하므로 $\binom{2n}{n}$입니다.

나쁜 경로 수 (반사 원리): 대각선을 넘는 "나쁜 경로"는 처음으로 $y = x + 1$에 도달하는 점 이후를 $y = x + 1$에 대해 반사시키면, $(0,0)$에서 $(n-1, n+1)$까지의 경로와 일대일 대응됩니다.

따라서 나쁜 경로 수는 $\binom{2n}{n-1}$이고:

유도 3: 생성함수 (요약)

점화식 $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$는 합성곱이므로 $C(x) = 1 + xC(x)^2$를 풀면:

(상세 유도는 카탈란 수 절 참조)

생성함수 심화

생성함수의 세 가지 주요 유형을 비교하고, 각각의 응용을 살펴봅니다.

보통 생성함수 vs 지수 생성함수

디리클레 급수 (Dirichlet Series)

수론적 함수 $f: \mathbb{N} \to \mathbb{C}$에 대한 디리클레 급수는 다음과 같이 정의됩니다.

두 수론적 함수의 디리클레 합성곱 $(f * g)(n) = \sum_{d \mid n} f(d) g(n/d)$에 대해:

대표적인 예:

$\sum_{d|n} \mu(d) = [n=1]$이라는 뫼비우스 함수의 핵심 성질은, 디리클레 급수로는 $\frac{1}{\zeta(s)} \cdot \zeta(s) = 1$이라는 간명한 형태로 표현됩니다.

생성함수 응용: 동전 교환 문제

1원, 5원, 10원, 50원짜리 동전으로 $n$원을 만드는 방법의 수를 구하는 문제입니다. 각 동전의 OGF는:

이 급수에서 $x^n$의 계수가 답입니다. 이는 정수 분할의 제한된 형태입니다.

포함-배제 원리 심화

포함-배제 원리의 고급 응용을 살펴봅니다.

교란 순열의 확률

$n$개의 원소를 무작위로 배열할 때, 어떤 원소도 제자리에 오지 않을 확률은:

놀랍게도 이 확률은 $n$이 커져도 거의 변하지 않습니다. $n = 5$일 때 이미 $\frac{44}{120} \approx 0.3667$로 극한값에 매우 가깝습니다.

오일러 피 함수의 포함-배제 유도 (상세)

$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$일 때, $\{1, 2, \ldots, n\}$ 중 $n$과 서로소인 수의 개수를 구합니다.

$A_i = \{m : 1 \le m \le n, \; p_i \mid m\}$로 놓으면 $|A_i| = n/p_i$이고:

포함-배제를 적용하면: