📂보조정리

조합론에서의 분할 원리

정리 ¹

다대일 함수의 정의

유한집합 $S$ 와 $T$ 과 자연수 $d \in \mathbb{N}$ 가 주어져 있다고 하자. 각각의 $s \in S$ 에 대해서 정확히 $d$ 개의 $t \in T$ 가 $f(t) = s$ 와 같이 대응되는 함수 $f : T \to S$ 를 $d$대일^$d$-to-one이라 한다.

분할 원리^{division principal}

유한집합 $S$ 와 $T$ 사이에 $d$대일 대응 $f : T \to S$ 가 존재하면 다음이 성립한다. $$ |S| = {\frac{ |T| }{ d }} $$ 여기서 $|X|$ 는 집합 $X$ 의 기수다.

설명

예를 들어 위의 그림과 같이 정의된 함수 $f$ 는 삼대일 대응이다.

다대일 대응은 그 이름 그대로 일대일대응^{one-to-one corresponding}의 일반화로, $d = 1$ 이면 정확히 단사^injective가 된다².

분할 원리는 다대일 대응의 정의에서 자연스럽게 얻을 수 있는 결론으로써, 별도의 증명은 생략한다.

예시: 원순열

분할 원리의 대표적인 응용으로써 원순열^{circular permutations}에 대해 알아보자. $n$ 개의 아이템이 있다고 할 때 이들을 일렬로 나열하는 것을 순열이라 하고, 그 경우의 수는 흔히 $_{n} P _{n} = n!$ 과 같이 나타낸다.

반면 원순열은 시작과 끝이 존재하지 않는 원탁에 이들을 나열하는 것으로써 정의되며, 배치 자체는 달라보일지라도 회전을 통해서 똑같은 폼을 갖출 수 있다면 같은 원순열로 본다. ‘원탁’이라든가 ‘회전’이라는 표현 없이 수학적으로 원순열을 따지려면 우선 다음과 같이 유한 리스트에 대한 쉬프트 오퍼레이터^{shift operator} $S$ 를 정의하는 방법이 있다. $$ \begin{align*} S :& \left( a_{1} , \cdots , a_{n} \right) \mapsto \left( a_{2} , \cdots , a_{n} , a_{1} \right) \\ S^{k} :=& S \circ S^{k-1} \end{align*} $$ 쉬프트 오퍼레이터는 보다시피 리스트의 첫 번째 아이템을 마지막으로 보내는 연산이고, 윗첨자는 오퍼레이터가 여러번 취해졌음을 의미한다. 이에 따르면 두 리스트 $L_{1}$ 과 $L_{2}$ 가 원순열의 맥락에서 같다는 동치관계 $L_{1} \equiv L_{2}$ 는 $L_{1} = S^{k} \left( L_{2} \right)$ 를 만족하는 자연수 $k$ 가 존재한다는 것과 동치로써 정의할 수 있다. 아이템의 수가 $n$ 일 때 리스트 $L$ 은 다음과 같이 $n$ 가지의 변형이 있다. $$ L \equiv S \left( L \right) \equiv \cdots \equiv S^{n-1} \left( L \right) $$ 이제 $T$ 를 단순히 $n$ 개의 아이템으로 만들어지는 순열의 집합으로 두고, $S$ 를 $n$ 개 아이템으로 만들어지는 원순열의 집합으로 두자. 이때 $f : T \to S$ 는 하나의 원순열 $s \in S$ 에 대해 $n$ 가지 순열 $t \in T$ 가 대응되는 $n$대일 대응이 된다. 분할 원리에 따르면 $S$ 의 기수는 다음과 같고, $S$ 의 기수는 곧 $n$ 개 아이템으로 만들어지는 원순열의 경우의 수가 된다. $$ \left| S \right| = {\frac{ \left| T \right| }{ n }} = \frac{ n! }{ n } = (n - 1)! $$