[조합론] 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)}$가 성립한다. 

참고자료:

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

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