조합론

조합론

이 글에서는 정수론과 선형대수학을 다루지 않습니다.

역원 구하기에 대해 읽어 보는 것이 도움이 될 수 있습니다.

[구체 수학](http://sereja.me/f/discrete_math_knuth.pdf 그레이엄, 커누스, 파타슈닉 저.

점화식 문제

하노이의 탑

123

요세푸스 문제

요세푸스 플라비우스(라틴어 Flavius Josephus)는 1세기의 저명한 역사가입니다. 전설에 따르면, 그에게 수학적 재능이 없었다면 그는 이름을 알리기 전에 목숨을 잃었을 것입니다.

유대-로마 전쟁 중에 그는 로마군에 의해 동굴에 갇힌 41명의 유대인 반란군 무리 가운데 한 명이었습니다. 포로가 되느니 차라리 자결을 택한 반란군은 원을 이루어 선 뒤, 원을 따라 돌면서 남은 사람 중 매 세 번째 사람을 아무도 남지 않을 때까지 죽이기로 결정했습니다. 그러나 요세푸스는 기소되지 않은 공모자 한 명과 함께 이런 자살 소동에 휘말리고 싶지 않았습니다. 그래서 그는 이 죽음의 원에서 자신과 친구가 어디에 서야 하는지를 재빨리 계산했습니다.

비둘기집 원리(디리클레 원리). 토끼들을 우리에 나누어 넣을 때 토끼의 수가 우리의 수보다 많다면, 적어도 한 우리에는 토끼가 두 마리 이상 들어 있습니다.

영어권에서는 Pigeonhole principle이라고 부르며 비둘기에 관해 이야기하지만, 본질은 같습니다.

이 원리는 자명해 보이지만, 그 적용이 항상 자명한 것은 아닙니다. 몇 가지 예를 살펴봅시다.

문제. $2 \times 2$ 정사각형과 그 내부의 점 $5$개가 주어집니다. 이들 중 두 점 사이의 거리가 $\leq \sqrt 2$인 두 점이 존재함을 증명하십시오.

풀이. $1 \times 1$ 크기의 작은 정사각형 $4$개를 생각해 봅시다. 비둘기집 원리에 의해 내부 또는 경계에 2개의 점이 있는 작은 정사각형이 존재합니다. 이 두 점이 구하는 점입니다.

좀 더 어려운 예는 다음과 같습니다:

  • 체스판을 도미노로 빈틈없이 덮으려고 합니다. 서로 마주 보는 두 모서리 칸을 제거하면 이것은 불가능해집니다.

  • 6명으로 이루어진 집단에는 항상 서로 친구이거나 서로 모르는 사이인 세 사람이 존재합니다.

  • 실제 사례: 어떤 무손실 압축 알고리즘도 가능한 모든 입력 파일에 대해 압축을 보장할 수는 없습니다.

포켓몬 문제.

뉴턴의 이항 정리

폴리=많음, 비=둘. nomen = 이름.

$$ (a + b)^n $$

전개식의 계수는 조합론에서 매우 중요한 역할을 합니다.

러시아에서는 이를 로 표기하고, 그 외의 모든 나라에서는 로 표기합니다.

어디가 $n$이고 어디가 $k$인지에 대해서조차 통일된 견해가 없다는 점이 몹시 짜증스럽습니다.

이항 계수

유클리드 알고리즘

체

파스칼의 삼각형

다음과 같은 사실을 알 수 있습니다

조합

주어진 집합의 원소 $k$개로 이루어진 순서 있는 묶음 중 원소가 반복될 수 있는 것을 $n$개의 원소에서 $k$개를 택하는 중복 순열이라고 합니다.

따라서 원소가 반복될 수 있으면, 그 집합을 중복 없는 순열 또는 간단히 순열이라고 합니다.

$n$개의 원소 중 $k$개를 고르는 조합이란 이 집합의 원소 $k$개로 이루어진 묶음을 말하며, 이때 원소의 순서만 다른 묶음은 같은 것으로 간주합니다(이 점에서 조합은 순열과 다릅니다).

마찬가지로, 조합에도 중복 조합과 중복 없는 조합이 있습니다.

«$n$개 중 $k$개를 고르는 조합»이라고 읽습니다.

계산하는 방법

int t[maxn];

int bp (int a, int n) {
    int ans = 1;
    while (n) {
        if (n&1) ans = ans*a % mod;
        a = a*a % mod;
        n >>= 1;
    }
    return ans;
}

int inv (int x) {
    return bp(x, mod-2);
}

int c (int n, int k) {
    return t[n]*inv(t[k]) % mod * inv(t[n-k]) % mod;
}

t[0] = 1;
for (int i = 1; i < maxn; i++)
    t[i] = i*t[i-1] % mod;

분할

공과 칸막이.

저자는 이 공식을 외우지 않으며 머릿속으로 대수 계산을 하려고 하지도 않고, 그저 보조 함수를 정의합니다:

int d(int n, int k) {
    return c(n + k - 1, k - 1);
}

잘 알려진 항등식

$$ \sum_k \binom{r}{m+k}\binom{s}{n-k} = \binom{r+s}{m+n} $$ $$ \sum_k \binom{l}{m+k} \binom{s}{n+k} = \binom{l+s}{l-m+n} $$ $$ \sum_k \binom{l}{m+k}\binom{s+k}{n} (-1)^k = (-1)^{l+m} \binom{s-m}{n-l} $$ $$ \sum_{k \leq l} \binom{l-k}{m}\binom{s}{k-n} (-1)^k = (-1)^{l+m} \binom{s-m-l}{l-m-n} $$ $$ \sum_{0 \leq k \leq l} \binom{l-k}{m}\binom{q+k}{n} = \binom{l+q+1}{m+n+1} $$

하키 스틱 항등식

«하키 스틱 항등식».

올바른 괄호 문자열

영 다이어그램

카탈랑 수

카탈랑 수는 놀라울 만큼 많은 조합론 문제에서 등장하는 수열입니다. 예를 들어, $n$번째 카탈랑 수는 다음의 개수와 같습니다:

  • …$n$개의 여는 괄호와 $n$개의 닫는 괄호로 이루어진 올바른 괄호 시퀀스

  • …n+1개의 리프를 가진 루트 있는 이진 트리(정점에 번호가 매겨져 있지 않은 경우)

  • …$(n+2)$각형인 볼록 다각형을 서로 교차하지 않는 대각선으로 삼각형들로 분할하는 방법의 수(이를 삼각분할이라고 합니다).

  • …원 위의 $2n$개의 점을 서로 교차하지 않는 $n$개의 현으로 연결하는 방법의 수.

  • …$n$개의 원소로 이루어진 구간을 연속된 블록으로 나누는 분할의 수.

  • …$n \times n$ 크기의 정사각 격자에서 점 $(0,0)$에서 점 $(n,n)$까지 가되 주대각선 위로 올라가지 않는 경로의 수.

0번째부터 시작하는 처음 몇 개의 카탈랑 수는 다음과 같습니다:

$$ 1, 1, 2, 5, 14, 42, 132, 429, 1430, … $$

카탈랑 수는 이차 시간 DP로 계산할 수 있습니다. $k$번째 카탈랑 수 $C_k$를 길이가 $2k$인, 즉 $k$쌍의 괄호로 이루어진 올바른 괄호 문자열의 개수라고 합시다. 괄호 문자열은 여는 괄호로 시작하며, 이 괄호에는 어떤 닫는 괄호가 대응합니다. 이 닫는 괄호의 위치(0부터 번호를 매길 때 모든 홀수 위치)를 모두 시도해 볼 수 있으며, 각 경우마다 괄호 문자열은 닫는 괄호 앞부분($k$쌍의 괄호로 이루어진)과 뒷부분($(n-1-k)$쌍으로 이루어진)의 두 올바른 괄호 문자열로 나뉩니다.

다음과 같은 점화식을 얻습니다:

$$ C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} $$

해석적 공식

하지만 그럴 필요는 없습니다. 지금부터 증명할 해석적 공식이 있기 때문입니다:

$$ C_n = \dfrac{1}{n+1} \dbinom {2n} {n} $$

이 공식은 단조 경로 문제에서 가장 쉽게 유도할 수 있습니다 —. n \times n 크기의 격자에서 단조 경로의 총 개수는 C_{2n}^{n}입니다. 이제 대각선을 넘는 단조 경로의 개수를 세어 봅시다. 그러한 경로 중 하나를 골라, 대각선보다 위에 있는 첫 번째 간선을 찾읍시다. 이 간선 이후에 이어지는 경로 전체를 대각선에 대해 대칭 이동합시다. 그 결과 (n-1) \times (n+1) 격자에서의 단조 경로를 얻습니다. 그런데 다른 한편으로, (n-1) \times (n+1) 격자의 모든 단조 경로는 반드시 대각선을 넘으므로, 이 경로는 n \times n 격자에서 대각선을 넘는 어떤(게다가 유일한) 단조 경로로부터 바로 이러한 방법으로 얻어진 것입니다. (n-1) \times (n+1) 격자에는 단조 경로가 C_{2n}^{n-1}개 있습니다. 결과적으로 다음 공식을 얻습니다:

$4 \times 4$ 정사각형 위의 $C_4 = 14$개 경로를 모두 나타내면 다음과 같습니다:

$$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C[...] $$

순열

그래프로서의 순열

다음과 같은 그래프

두 순열의 최장 공통 부분 수열.

첫 번째 순열에서 원소들이 순서대로 나오도록 원소들의 이름을 바꾸어도 아무런 문제가 없습니다.

조합적 대상의 생성

역문제

«앵무새» 문제. 어떤 정보 64바이트를 전달해야 합니다. 이를 위해 특별히 훈련된 앵무새 320마리가 있으며, 각 앵무새는 0부터 255까지의 수 하나를 기억할 수 있습니다. 모든 앵무새는 언젠가는 목적지에 도착하여 자신의 바이트를 전달하지만, 풀려난 순서와 다른 순서로 도착할 수도 있습니다. 앵무새들은 겉보기에 서로 구별할 수 없습니다.

포함-배제 원리

이는 누적 합을 이용해 다차원 도형의 넓이를 계산할 때 유용합니다.

다음 단계, 또는 다루지 않은 유용한 주제

어떤 이유로든 필요하시다면 참고하십시오.

번사이드 보조정리.

군론 없이는 이해하기가 매우 어렵지만, 유효한 루빅스 큐브의 개수처럼 매우 자명하지 않은 것들을 셀 수 있게 해 줍니다.

선형 점화식.

정수론.

부분 순서 집합과 딜워스 정리.

생성 함수. 많은 조합적 값에 대한 명시적인 공식을 찾을 수 있게 해 주는 매우 흥미로운 대수적 기법입니다.

조합론과 그래프 이론의 경계에 있는 여러 개별적인 사실들.

확률론과의 경계에 있는 조합론.


← ../정수론

../확률론 →