집합의 분할

원문 보기: https://dawoum.duckdns.org/wiki/집합의_분할

Main article: Stirling numbers of the second kind

조합은 서로 다른 \(n\)개의 대상에서 원하는 \(k\)개를 선택하는 방법의 수입니다. 조금 다르게, 예를 들어, 서로 다른 4개의 물건을 2 사람에게 나누어주는 경우의 수를 생각해 보십시오. 이때에는 0개를 주는 것은 나누어주는 것이 아니기 때문에 제외합니다. 그렇기 때문에 1:3 또는 2:2로 나눌 수 있습니다.

먼저, 서로 다른 4개를 1:3으로 나누는 것의 방법의 수를 알아보겠습니다.

\(\quad\)\(C(4,1) \times C(3,3)\)

이와 같이 먼저 4개 중에 1개를 선택하고, 나머지 3개를 한 묶음으로 만들 수 있습니다. 이것을 볼 때에는 뒤의 \(C(3,3)=1\)이기 때문에 할 필요가 없을 것으로 보입니다. 그렇지만, 이것이 전체에서 선택하는 조합이 아니라, 전체를 2로 나누는 분할이라는 것을 나타내기 위해서 필요합니다. 또한, 서로 다른 4개를 3:1로 나누는 것은 경우의 수가 같습니다. 즉,

\(\quad\)\(C(4,3) \times C(1,1)\)

반면에, 서로 다른 4개를 2:2로 나누는 것은 앞의 경우와 차이점이 발생합니다. 단순히 위의 경우를 생각한다면, 다음과 같은 경우의 수를 가진다고 생각할 수 있습니다:

\(\quad\)\(C(4,2) \times C(2,2)\).

어쨌든, 이것은 잘못 계산된 것입니다. 왜냐하면, 1:3 또는 3:1과 같은 경우는 서로 가진 크기가 다르기 때문에, 순서를 바꾸더라도 상관이 없습니다.

\(\quad\)\(\{a\}, \{b, c, d\}\)

\(\quad\)\(\{b\}, \{a, c, d\}\)

\(\quad\)\(\{c\}, \{a, b, d\}\)

\(\quad\)\(\{d\}, \{a, b, c\}\)

그러나, 2:2로 나눌 때에는 다음과 같이 쓸 수 있습니다:
\(\quad\)\(\color{Red}\{a, b \}, \{c, d \}\)

\(\quad\)\(\color{Cyan}\{a, c \}, \{b, d \}\)

\(\quad\)\(\color{Green}\{a, d \}, \{b, c \}\)

\(\quad\)\(\color{Green}\{b, c \}, \{a, d \} \)

\(\quad\)\(\color{Cyan}\{b, d \}, \{a, c \}\)

\(\quad\)\(\color{Red}\{c, d \}, \{a, b \}\)

앞의 열만 볼 때에는 조합 \(C(4,2)\)입니다. 그러나, 분할로 볼 때에는 같은 색깔끼리 같은 경우를 나타냅니다. 이것은 분할하는 크기가 같기 때문에 발생하고, 같은 크기가 발생하는 횟수의 팩토리얼만큼 같은 경우가 발생합니다. 즉, 이 경우에 맞는 경우의 수는 다음과 같습니다.

\(\quad\)\(\displaystyle C(4,2) \times C(2,2) \times \frac{1}{2!}\).

이것은 원순열 또는 같은 것이 있는 순열에서와 마찬가지 이유로, 선택의 순서가 바뀌게 되면 같은 경우가 발생하고, 이것을 1개로 세기 위해서 나눗셈을 해야 합니다.

예를 들어, 서로 다른 6개를 2:2:2로 나눌 때에는 다음과 같습니다:

\(\quad\)\(\displaystyle C(6,2) \times C(4,2) \times C(2,2) \times \frac{1}{3!}\).

이 경우에서, 다음의 세 개의 그룹이 뽑히는 순서에 상관없이 같은 1가지 경우에 해당하기 때문입니다.

\(\quad\)\(\{a, b \}, \{c, d \}, \{e, f\}\)

물론, 서로 다른 6개를 3:3으로 나눌 때에는 다음과 같습니다:

\(\quad\)\(\displaystyle C(6,3) \times C(3,3) \times \frac{1}{2!}\).

또한, 서로 다른 6개를 1:2:3으로 나눌 때에는 다음과 같습니다:

\(\quad\)\(C(6,1) \times C(5,2) \times C(3,3)\).

만약 중복되는 경우가 여러 번 나타날 때에는 어떻게 계산할까요? 예를 들어, 서로 다른 16개를 2:2:2:3:3:4로 나누는 방법의 수는 얼마일까요? 계산의 편의를 위해서 가능한 작은 숫자로 배열하는 것이 좋습니다.

\(\quad\)\(\displaystyle C(16,2)\times C(14,2) \times C(12,2)\times C(10,3) \times C(7,3) \times C(4,4) \times \frac{1}{3!} \times \frac{1}{2!}\).

이와 같은 경우를 집합으로 표현하면,

\(\quad\)원소 \(n\)개를 가진 유한집합을 공집합이 아닌 서로소인 \(k\)개의 부분집합으로 나누는 것이며,

\(\quad\)이를 집합의 분할이라고 부르며,

\(\quad\)이를 \(S(n,k)\) 또는 \(\lbrace\textstyle{n\atop k}\rbrace\)로 나타내고, 다음과 같이 계산될 수 있습니다:

\(\quad\)\(\displaystyle \left\{ {n \atop k}\right\} = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n\)

\(\quad\)또는 \(\displaystyle S(n,k)=\frac{1}{k!}\sum_{j=0}^{k} (-1)^{j} \binom{k}{j} (k-j)^n\).

집합의 분할에 대한 공식이 알려져 있지만, 숫자가 많지 않을 때에는 직접 계산하는 것이 편할 수 있습니다. 예를 들어, 위에서 소개한 \(S(4,2)\)는 1:3(또는 3:1)과 2:2로 나누는 두 가지 경우가 있습니다. 그러므로 \(S(4,2)=4+3=7\)의 경우의 수를 가집니다. 한편, 위의 공식을 적용할 때, 경우의 수는 다음과 같습니다.

\(\quad\)\(\displaystyle \left\{ {4 \atop 2}\right\} = \frac{1}{2!}\sum_{j=0}^{2} (-1)^{2-j} \binom{2}{j} j^4\)

\(\quad\)\(\displaystyle =\frac{1}{2!}\left((-1)^{2}\binom{2}{0} 0^4+(-1)^{1}\binom{2}{1} 1^4+ (-1)^{0}\binom{2}{2} 2^4\right)\)

\(\quad\)\(\displaystyle =\frac{1}{2!}(0-2+16)=7\)

시그마에서 \(j = 0\)인 경우에는 항상 영이므로 할 필요가 없지만, 관련된 다른 스털링 숫자와 일관성을 유지하기 위해서 영부터 시작하는 것으로 보입니다. 그리고 잘 외워지지 않을 것처럼 보이는 이 공식을 굳이 암기할 필요까지는 없어 보입니다.

다른 예제

\(S(5,3)\)과 같이 더 많은 부분집합으로 나눌 때에는 어떻게 계산할까요? 

• 먼저 분할의 경우를 찾습니다.
• 각 경우별로 경우의 수를 구합니다.
• 경우의 수를 더합니다.

분할의 경우를 찾을 때에는, 적은 숫자부터 시작하는 것이 좋습니다. 세 부분으로 나누어야 하기 때문에 첫 번째와 두 번째 1개씩 주고, 나머지를 세 번째에 둡니다. 이것의 순서를 바꾸는 것은 동일하기 때문에 별도로 사고할 필요가 없습니다.

\(\quad\)1:1:3

다음에는 맨 마지막에서 1개를 앞으로 가져옵니다.

\(\quad\)1:2:2

이때 뒤의 숫자보다 앞의 숫자가 클 수는 없기 때문에 여기서 멈춥니다. 즉, 위의 두 경우 외에는 없습니다.

다른 경우로 \(S(7,3)\)을 분할하는 경우는 어떤 것이 있을까요?

\(\quad\)1:1:5 → 7×6×1×\(\frac12\)=21

\(\quad\)1:2:4 → 7×15×1=105

\(\quad\)1:3:3 → 7×20×1×\(\frac12\)=70

\(\quad\)2:2:3 → 21×10×1×\(\frac12\)=105

방법의 수는 21+105+70+105=301입니다.

하는 방법이 보이시나요? 3행까지는 맨 끝의 두 개를 하나씩 앞으로 보내는 경우이고, 작거나 같을 때까지 할 수 있습니다. 4행은 그 앞의 두 개를 비교해서 같은 작업을 합니다. 한편, 위의 두 번째 공식을 이용해서 값이 같은지 확인해 보겠습니다.

\(\quad\)\(\displaystyle S(7,3)=\frac{1}{3!}\sum_{j=0}^{3} (-1)^{j} \binom{3}{j} (3-j)^7\)

\(\quad\)\(\displaystyle =\frac{1}{3!}\left(\binom{3}{0} 3^7-\binom{3}{1} 2^7 + \binom{3}{2} 1^7 - \binom{3}{3} 0^7\right)=301\)

두 번째 공식이 조금 더 적용하기가 쉽습니다.

재귀 관계

집합의 분할이 쉽지 않기 때문에, 좀 더 계산이 쉬운 방법이 필요합니다. 몇 가지 항등식이 있지만, 여기서는 재귀 관계에 대해 소개하고자 합니다.

\(\quad\)\(S(n,k)=S(n-1,k-1)+kS(n-1,k)\)

이 식은 두 부분으로 나뉩니다.

1. 임의의 원소 한 개만을 가진, 예를 들어 \(\{a\}\), 부분집합을 분할하고, 나머지 \(n–1\)개의 원소를 \(k–1\)개로 분할하는 앞부분,
2. \(n–1\)개를 \(k\)개로 분할한 후에, 임의의 원소, 예를 들어 \(a\)를 \(k\)개의 분할 중에 하나에 포함시키는 뒷부분.

위의 예제에서 사용한 \(S(7,3)\)은 아래와 같이 만든 후에, 뒤에서 앞부터 계산해와야 합니다.

\(\quad\)\(S(7,3)=S(6,2)+3S(6,3)=301\)

\(\quad\)\(S(6,3)=S(5,2)+3S(5,3)=90\)

\(\quad\)\(S(5,3)=S(4,2)+3S(4,3)=25\)

\(\quad\)\(S(4,3)=S(3,2)+3S(3,3)=6\)

\(\quad\)\(S(6,2)=S(6,1)+2S(5,2)=31\)

\(\quad\)\(S(5,2)=S(5,1)+2S(4,2)=15\)

\(\quad\)\(S(4,2)=S(4,1)+2S(3,2)=7\)

\(\quad\)\(S(3,2)=S(3,1)+2S(2,2)=3\)

이런 값을 구할 때, \(S(n,0)=0, S(n,1)=1, S(n,n)=1\)을 이용합니다.

분할과 분배

크리스마스 선물로 서로 다른 사탕 10개를 샀습니다. 세 명에게 2:3:5개로 나누는 방법의 수는 몇 개일까요?

분할은 서로 다른 10개를 2:3:5로 나누는 과정입니다.

\(\quad\)\(C(10,2)\times C(8,3) \times C(5,5)\)

분배는 10개를 2:3:5로 나눈 후에 A, B, C 세 사람에게 나누는 과정까지를 말합니다:

\(\quad\)\(C(10,2)\times C(8,3) \times C(5,5) \times 3!\)

대진표 문제1

6개 팀이 참가한 대회의 그림과 같은 대진표를 완성하는 경우의 수는?
보통 대진표는 분배의 문제입니다. 대진표의 경우의 수는 위에서 밑으로 분배하는 방법과 아래에서 위로 올라가면서 분배하는 방법이 있습니다.

위에서 아래로

대진표-(가)를 위에서 밑으로 분배할 때에는 제일 위의 선(결승)에서 왼쪽, 오른쪽이 3:3입니다. 분할을 합니다.

\(\quad\)\(\displaystyle C(6,3)\times C(3,3)\times \frac{1}{2!}=10\)

분배는 왼쪽과 오른쪽에 3팀을 보내는 것은 1가지로 셉니다. 왜냐하면, 왼쪽-오른쪽으로 ABC:DEF와 DEF:ABC는 구별이 되지 않기 때문입니다.

이제 왼쪽의 3팀을 1:2로 분할하고, 오른쪽 3팀도 1:2로 분할합니다.

\(\quad\)\(C(3,1) \times C(2,2)=3\)

\(\quad\)\(C(3,1) \times C(2,2)=3\)

왼쪽에 1:2로 분할된 것을 분배하는 것은 1가지입니다. 왜냐하면 A-BC로 분배되었을 때, A는 무조건 1팀이 있는 곳에 가야 하고, BC는 두 번째에 놓이는데, B-C로 적는 것과 C-B로 적는 것은 결국 BC가 경기한다는 것을 나타내기 때문입니다.

오른쪽도 같은 이유로 1가지입니다.

위의 과정은 모두 연이어 발생하기 때문에 곱의 법칙을 적용해야 합니다.

\(\quad\)\(10\times 3\times 3=90\)

아래에서 위로

아래에서 위로 올라갈 때에는 밑 아래의 대진하는 경우를 봅니다. 6팀이 1:2:2:1로 구성되어 있으며, 다음과 같이 분할합니다.

\(\quad\)\(\displaystyle C(6,1) \times C(5,2) \times C(3,2) \times (1,1) \times \frac{1}{2!}\times {2!}=45\)

이제 분배를 해서 대진표를 완성해야 합니다. 예를 들어 A:BC:DE:F로 분할이 되었다고 가정해 보겠습니다.

• 먼저 A를 대진표에 넣을 때에는 가장 앞쪽과 끝쪽이 있지만, 상대가 없기 때문에 어디로 가더라도 1가지입니다. 맨 앞에 적습니다.
• 자연스럽게 F는 A가 가지 않은 곳으로 가야 하기 때문에 1가지입니다. 끝에 적습니다.
• BC를 분배할 때에는 A와 F가 적혀 있기 때문에 2가지입니다. A가 있는 조에 속할지 F가 있는 조에 속할지 결정해야 합니다.
• 자연스럽게 DE는 남아 있는 자리에 가기 때문에 1가지입니다.

위의 과정도 연이어 발생하기 때문에 곱의 법칙을 적용해야 합니다.

\(\quad\)\(45\times 2=90\)

대진표 문제2

오른쪽 대진표를 완성하는 경우의 수는 몇 가지일까요?

위에서 아래로

\(\quad\)\(\displaystyle C(6,2)\times C(4,4) \times C(4,2) \times C(2,2) \times \frac{1}{2!} = 45\)

아래에서 위로

\(\quad\)\(\displaystyle C(6,2)\times C(4,2) \times C(2,2) \times \frac{1}{3!} \times C(3,1)=45\)