[조합론] 8. 분할, 스털링 수

[조합론] 8. 분할, 스털링 수

집합 \(S\)의 공집합이 아닌 부분집합 \(S_{1},\,S_{2},\,\cdots,\,S_{r}\)에 대하여

(1) \(S_{i}\cap S_{j}=\emptyset\,(i\neq j)\)

(2) \(\displaystyle S=\bigcup_{i=1}^{r}{S_{i}}\)

를 만족할 때, \(\displaystyle\bigcup_{i=1}^{r}{S_{i}}\)를 집합 \(S\)의 분할(partition)이라고 한다.

예를들어 집합 \(\{1,\,3,\,5,\,7\}\cup\{2,\,4,\,6,\,8\}\)은 집합 \(\{1,\,2,\,3,\,4,\,5,\,6,\,7,\,8\}\)의 한 분할이다.

예: 52장의 카드에서 13장씩 네 묶음으로 나누는 경우의 수는?

풀이: 먼저 13장을 고르는 경우의 수는 \(\displaystyle\binom{52}{13}\)이고, 남은 39장에서 13장을 고르는 경우의 수는 \(\displaystyle\binom{39}{13}\), 남은 26장에서 13장을 고르는 방법의 수는 \(\displaystyle\binom{26}{13}\), 마지막으로 남은 13장을 모두 고르면 되고, 분할을 나열하는 경우의 수가 \(4!\)이므로 네 묶음으로 나누는 방법의 수는$$\binom{52}{13}\binom{39}{13}\binom{26}{13}\cdot\frac{1}{4!}=\frac{52!}{13!39!}\frac{39!}{13!26!}\frac{26!}{13!13!}\frac{1}{4!}=\frac{52!}{(13!)^{4}4!}$$이다.

이 결과를 일반화하면 \(mn\)개의 원소를 갖는 집합에서 \(n\)개의 원소를 갖는 부분집합 \(m\)개로 분할하는 경우의 수가 \(\displaystyle\frac{(mn)!}{(n!)^{m}m!}\)임을 알 수 있다.

집합 \(\{1,\,2,\,\cdots,\,n\}\)에서 \(\{1,\,2,\,\cdots,\,n\}\)으로 가는 전단사함수 \(\sigma\)를 이 집합의 치환(permutation)이라 하고$$\sigma=\begin{pmatrix}1&2&\cdots&n\\ \sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}$$으로 나타낸다. 이때 치환은 \(n!\)개 존재한다.

순열 3412를 나타내는 치환은 \(\displaystyle\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}\)이고, \(1\rightarrow3\rightarrow1\), \(2\rightarrow4\rightarrow2\)로 나누어진다. 이 두가지를 사이클(cycle)이라 하고, 각각 \((1,\,3),\,(2,\,4)\)로 나타내고, \(\displaystyle\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}=(1\,3)(2\,4)\)이다.

집합 \(\{1,\,2,\,3,\,4\}\)에 대해 다음과 같이 2개의 사이클로 구성된 11개의 치환이 존재한다.$$\begin{align*}\begin{pmatrix}1&2&3&4\\2&3&1&4\end{pmatrix}&=(1\,2\,3)(4),\,\begin{pmatrix}1&2&3&4\\3&1&2&4\end{pmatrix}=(1\,3\,2)(4),\,\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}=(1\,3\,4)(2)\\ \begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}&=(1\,4\,3)(2),\,\begin{pmatrix}1&2&3&4\\2&4&3&1\end{pmatrix}=(1\,2\,4)(3),\,\begin{pmatrix}1&2&3&4\\4&1&3&2\end{pmatrix}=(1\,4\,2)(3)\\ \begin{pmatrix}1&2&3&4\\1&3&4&2\end{pmatrix}&=(2\,3\,4)(1),\,\begin{pmatrix}1&2&3&4\\1&4&2&3\end{pmatrix}=(2\,4\,3)(1),\,\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}=(1\,2)(3\,4)\\ \begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}&=(1\,3)(2\,4),\,\begin{pmatrix}1&2&3&4\\4&3&2&1\end{pmatrix}=(1\,4)(2\,3)\end{align*}$$

 

\(k\)개의 사이클로 나타내어지는 원소의 개수가 \(n\)인 집합에 대한 치환의 개수를 제 1종 스털링 수(the Stirling numbers of the first kind)라 하고 \(s(n,\,k)\)로 나타낸다. 위의 예에서 \(s(4,\,2)=11\)이다.

정리: \(0<k<n\)에 대하여$$s(n,\,k)=s(n-1,\,k-1)+(n-1)s(n-1,\,k)$$이다.

증명: \(k\)개의 사이클로 이루어진 집합 \(\{1,\,2,\,\cdots,\,n\}\)의 치환은 다음의 두가지 경우로 나뉘어진다.

(1) \(n\)이 혼자 사이클을 이루는 경우: \(n\)을 제외한 \(k-1\)개의 사이클로 이루어진 \(\{1,\,2,\,\cdots,\,n-1\}\)의 치환이므로 그 개수는 \(s(n-1,\,k-1)\)이다.

(2) \(n\)이 다른 수와 사이클을 이루는 경우: \(k\)개의 사이클로 이루어진 집합 \(\{1,\,2,\,\cdots,\,n-1\}\)의 치환의 개수는 \(s(n-1,\,k)\)이다. 각 치환에 대하여 \(n\)을 \(1,\,2,\,\cdots,\,n-1\)중 하나의 왼쪽에 두면 \(n\)이 다른 수와 함께 사이클을 이루는 경우를 얻고, \(n\)을 \(1,\,2\,\cdots,\,n-1\)중 하나의 왼쪽에 두는 방법은 \(n-1\)가지이므로 따라서 \((n-1)s(n-1,\,k)\)가지의 경우가 있다.

(1), (2)에 의해 \(s(n,\,k)=s(n-1,\,k-1)+(n-1)s(n-1,\,k)\)가 성립한다.

예: 집합 \(\{1,\,2,\,3,\,4\}\)의 11개의 치환을 다음과 같이 나눌 수 있다.

(1) 4가 혼자 사이클을 이루는 경우:$$\begin{pmatrix}1&2&3&4\\2&3&1&4\end{pmatrix}=(1\,2\,3)(4),\,\begin{pmatrix}1&2&3&4\\3&1&2&4\end{pmatrix}=(1\,3\,2)(4)$$이므로 \(s(3,\,1)=2\)이다.

(2) 4가 다른 수와 함께 사이클을 이루는 경우: 2개의 사이클로 이루어진 \(\{1,\,2,\,3\}\)의 치환은$$(1)(2\,3),\,(2)(1\,3),\,(3)(1\,2)$$3가지\((=s(3,\,2))\)이고, 각각의 경우에 \(4\)를 넣는 경우는 3가지이므로 4가 다른 수와 함께 사이클을 이루는 경우의 수는 \(3s(3,\,2)=9\)이다.

\(s(4,\,2)=11\)이므로 따라서 \(s(4,\,2)=11=2+9=s(3,\,1)+3s(3,\,2)\)이다.

\(n\)개의 원소를 갖는 집합의 분할에서 정확히 \(k\)개의 집합으로 나누는 방법의 수를 제 2종 스털링 수(the Stirling numbers of the second kind)라 하고 \(S(n,\,k)\)로 나타낸다.

\(n\geq1\)일 때, \(S(n,\,1)=S(n,\,n)=1\)이고 집합 \(\{1,\,2,\,3,\,4\}\)를 2개의 부분집합으로 나누면$$\begin{matrix}\{1,\,2\}\cup\{3,\,4\},&\{1,\,3\}\cup\{2,\,4\},&\{1,\,4\}\cup\{2,\,3\},&\{1,\,2,\,3\}\cup\{4\}\\ \{1,\,2,\,4\}\cup\{3\},&\{1,\,3,\,4\}\cup\{2\},&\{2,\,3,\,4\}\cup\{1\},&\end{matrix}$$이므로 \(S(4,\,2)=7\)이다.

정리: \(0<k<n\)에 대하여$$S(n,\,k)=S(n-1,\,k-1)+kS(n-1,\,k)$$이다.

증명: 집합 \(\{1,\,2,\,\cdots,\,n\}\)을 \(k\)개의 집합으로 나누는 방법은 다음의 두가지 경우로 나뉘어진다.

(1) \(n\)번째 원소가 하나의 부분집합을 이루는 경우: 나머지 \(n-1\)개의 원소를 \(k-1\)개의 부분집합으로 나누면 \(k\)개의 부분집합이 생기므로 이 경우의 수는 \(S(n-1,\,k-1)\)이다.

(2) \(n\)번째 원소가 다른 원소와 함께 부분집합을 이루는 경우: 나머지 \(n-1\)개의 원소를 \(k\)개의 부분집합으로 나누고 \(n\)번째 원소를 이들 집합 중 하나에 포함시키면 \(kS(n-1,\,k)\)가지의 경우가 발생한다.

따라서 (1), (2)에 의해 \(S(n,\,k)=S(n-1,\,k-1)+kS(n-1,\,k)\)가 성립한다.

예:$$\begin{align*}S(4,\,2)&=S(3,\,1)+2S(3,\,2)\\&=1+2(S(2,\,1)+S(2,\,2))\\&=1+2(2+1)\\&=7\end{align*}$$

정리: \(n\geq2\)일 때 \(S(n,\,2)=2^{n-1}-1\)이다.

증명: 수학적 귀납법을 이용하여 증명하자.

(i) \(n=2\)일 때, \(S(2,\,2)=1=2^{2-1}-1\)이므로 \(n=2\)일 때 등식이 성립한다.

(ii) \(n=k\,(k\geq2)\)일 때, 이 등식이 성립한다고 가정하자. 그러면$$\begin{align*}S(k+1,\,2)&=S(k,\,1)+2S(k,\,2)\\&=1+2(2^{k-1}-1)\\&=2^{k}-1\\&=2^{(k+1)-1}-1\end{align*}$$이므로 \(n=k+1\)일 때도 등식이 성립한다.

정리: \(m,\,n\geq1\)일 때, \(|X|=m,\,|Y|=n\)이라 하자.

(1) 집합 \(X\)에서 집합 \(Y\)로의 함수 중에서 치역의 원소의 개수가 \(k\)개인 함수의 개수는 \(\displaystyle S(m,\,k)\binom{n}{k}k!=S(m,\,k)_{n}P_{k}\)이다.

(2) 집합 \(X\)에서 집합 \(Y\)로의 함수의  총 개수는 \(\displaystyle n^{m}=\sum_{k=1}^{n}{S(m,\,k)_{n}P_{k}}\)이다.

(3) 집합 \(X\)에서 집합 \(Y\)로의 전사함수의 개수는 \(n!S(m,\,n)\)이다.

증명:

(1) 집합 \(X\)를 \(k\)개의 집합으로 분할하는 경우의 수는 \(S(n,\,k)\)이고, 집합 \(Y\)의 원소 중 \(k\)개의 원소를 선택해서 치역이 되게 하는 경우의 수는 \(\displaystyle\binom{n}{k}\), 분할된 \(k\)개의 집합들을 치역으로 선택된 \(k\)개의 원소에 대응하는 경우의 수는 \(k!\)이므로 치역의 원소가 \(k\)개인 함수의 개수는 \(\displaystyle S(m,\,k)\binom{n}{k}k!=S(m,\,k)_{n}P_{k}\)이다.

(2) (1)에 의해 성립한다.

(3) 집합 \(X\)를 \(n\)개의 집합으로 분할하고, 이 분할된 집합을 집합 \(Y\)의 원소에 일대일로 대응시키면 \(X\)에서 \(Y\)로의 전사함수가 된다. 이때 집합 \(X\)를 \(n\)개의 집합으로 분할하는 경우의 수는 \(S(m,\,n)\)이고, \(n\)개의 분할된 집합들을 집합 \(Y\)의 원소에 일대일로 대응시키는 경우의 수는 \(n!\)이므로 따라서 전사함수의 개수는 \(n!S(m,\,n)\)이다.

\(n\)개의 원소를 갖는 집합을 분할(\(1,\,2,\,\cdots,\,n\)개의 집합으로 분할)하는 경우의 수를 벨수(Bell number)라 하고 \(B(n)\)으로 나타낸다. \(\displaystyle B(n)=\sum_{k=1}^{n}{S(n,\,k)},\,B(0)=S(0,\,0)=0\)이 성립한다.

정리: \(n\geq1\)일 때,$$B(n)=\sum_{k=1}^{n}{S(n,\,k)}$$가 성립한다.

증명: \(n\)개의 원소 중 하나를 \(a\)라고 하면, 집합의 분할에서 \(a\)를 포함하는 집합의 다른 원소들의 개수가 \(0,\,1,\,\cdots,\,n-1\)개 가능하다. 임의의 \(j=0,\,1,\,\cdots,\,n-1\)에 대하여 \(a\)를 포함하는 집합의 다른 원소들의 개수가 \(j\)개인 분할의 개수는 \(\displaystyle\binom{n-1}{j}B(n-j-1)\)이고 따라서$$B(n)=\sum_{j=0}^{n-1}{\binom{n-1}{j}B(n-j-1)}=\sum_{k=0}^{n-1}{\binom{n-1}{k}B(k)}$$이다.

\(n\)개의 원소를 갖는 집합을 \(k\)개 이하의 집합들로 분할(\(1,\,2,\,\cdots,\,k\)개의 집합으로 분할)하는 방법의 수를 \(B(n,\,k)\)로 나타낸다.

(1) \(n\)명의 사람들을 서로 다른 \(k\)개의 방에 빈방 없이 배치하는 방법의 수: \(S(n,\,k)k!\)

(2) \(n\)명의 사람들을 서로 다른 \(k\)개의 방에 배치하는 방법의 수(빈방 가능): \(k^{n}\)

(3) \(n\)명의 사람들을 \(k\)개의 그룹으로 나누는 방법의 수: \(S(n,\,k)\)

(4) \(n\)명의 사람들을 \(k\)개 이하의 그룹으로 나누는 방법의 수: \(\displaystyle B(n,\,k)=\sum_{i=1}^{k}{S(n,\,k)}\)

\(f_{k}(x)\)를 \(k\)를 고정했을 때, 제 2종 스털링 수 \(S(n,\,k)\)의 생성함수라고 하자. 그러면$$\begin{align*}f_{k}(x)&=\sum_{n=0}^{\infty}{S(n,\,k)x^{n}}\\&=\sum_{n=0}^{\infty}{\{S(n-1,\,k-1)+kS(n-1,\,k)\}x^{n}}\\&=xf_{k-1}(x)+kxf_{k}(x)\end{align*}$$이고$$\begin{align*}f_{k}(x)&=\frac{x}{1-kx}f_{k-1}(x)=\frac{x}{1-kx}\frac{x}{1-(k-1)x}f_{k-2}(x)\\&=\cdots\\&=\frac{x}{1-x}\frac{x}{1-2x}\cdots\frac{x}{1-kx}\\&=x^{k}\sum_{j=1}^{k}{\frac{a_{j}}{1-jx}}\end{align*}$$여기서$$\begin{align*}a_{r}&=\frac{1}{1-\frac{1}{r}}\frac{1}{1-\frac{2}{r}}\cdots\frac{1}{1-\frac{r+1}{r}}\cdots\frac{1}{1-\frac{k}{r}}\\&=\frac{r}{r-1}\frac{r}{r-2}\cdots\frac{r}{1}\frac{r}{-1}\cdots\frac{r}{r-k}\\&=r^{k-1}(-1)^{k-r}\frac{1}{(k-r)!}\frac{1}{(r-1)!}\\&=\frac{(-1)^{k-r}r^{k}}{(k-r)!r!}\end{align*}$$이므로$$S(n,\,k)=\sum_{r=1}^{k}{a_{r}r^{n-k}}=\sum_{r=1}^{k}{\frac{(-1)^{k-r}r^{k}}{(k-r)!r!}r^{n-k}}=\sum_{r=1}^{k}{(-1)^{k-r}\frac{r^{n}}{(k-r)!r!}}$$이고$$\begin{align*}B(n,\,k)&=\sum_{k=1}^{n}{S(n,\,k)}=\sum_{k=1}^{n}{\sum_{r=1}^{k}{\frac{(-1)^{k-r}r^{n}}{(k-r)!r!}}}\\&=\sum_{r=1}^{n}{\sum_{k=r}^{n}{\frac{(-1)^{k-r}r^{n}}{(k-r)!r!}}}=\sum_{r=1}^{n}{\frac{r^{n}}{r!}}\sum_{s=1}^{n-r}{\frac{(-1)^{s}}{s!}}\\&=\frac{1}{e}\sum_{r=1}^{\infty}{\frac{r^{n}}{r!}}\end{align*}$$이다.

자연수 \(n\)에 대하여 원소의 합이 \(n\)이 되는 자연수들로 이루어진 집합을 자연수 \(n\)의 분할이라고 한다. 자연수 \(n\)의 분할들의 개수를 \(p(n)\)이라 하고, \(n\)을 \(k\)개의 자연수들로 분할하는 방법의 수를 \(p(n,\,k)\)로 나타낸다.

예: \(\{5,\,3,\,3,\,2,\,1,\,1,\,1\}\)은 자연수 16의 분할이다.

예: 4는 다음과 같이 나타낼 수 있으므로 \(p(4)=5\)이고 \(p(4,\,2)=2\)이다.$$\begin{align*}4&=4\\&=3+1\\&=2+2\\&=2+1+1\\&=1+1+1+1\end{align*}$$또한 \(p(n,\,1)=p(n,\,n)=p(n,\,n-1)=1\)이고 \(\displaystyle p(n,\,2)=\left\lfloor\frac{n}{2}\right\rfloor\)이다.

예: 5개의 같은 공을 4개의 같은 바구니에 넣되 빈 바구니를 허용하는 경우의 수는$$p(5,\,1)+p(5,\,2)+p(5,\,3)+p(5,\,4)=1+2+2+1=6$$가지 이고, 빈 바구니를 허용하지 않는 경우는$$p(5,\,4)=1$$가지 이다.

정리: \(\displaystyle\sum_{i=1}^{k}{p(n,\,i)}=p(n+k,\,k)\)이다.

증명: \(i\)개의 자연수의 합으로 표현되는 \((j_{1},\,j_{2},\,\cdots,\,j_{n})\)형태의 \(n\)의 분할에 \(k\)개의 자연수의 합으로 표현되는 \((k-i,\,j_{1},\,j_{2},\,\cdots,\,j_{n},\,0,\,\cdots,\,0)\)형태의 \(n+k\)의 분할들을 대응시키면 \(\displaystyle p(n+k,\,k)=\sum_{i=1}^{k}{p(n,\,i)}\)가 성립한다. 

참고자료:

조합론과 그래프이론, 조성진, 김한두, 경문사

조합 및 그래프이론, 김정진, 교우사