1 개요
조합과 관련된 내용이다. 분할에는 자연수의 분할과 집합의 분할이 있다. 한마디로 자연수와 집합을 조합을 이용해 나누는 방법.
대한민국의 고등학교 수학 교과목에는 제7차 교육과정에서 이산수학에 있었다가 2007 개정 교육과정에서 아예 삭제되었고 2009 개정 교육과정에서 확률과 통계에 편입되었다. 2015 개정 교육과정(문·이과 통폐합 교육과정)에서부터 다시 대학교 과정으로 쫓겨난다.
2 종류
2.1 자연수의 분할
자연수 [math]n[/math]을 [math]r[/math]개의 자연수의 합으로 나타내는 가짓수를 [math]P\left(n,r\right)[/math]로 표기한다[1]. 이때 순서는 생각하지 않는다. 예를 들어 [math]5[/math]를 [math]3[/math]개의 자연수로 나누면 [math]5=3+1+1=2+2+1[/math] 이므로 [math]P\left(5,3\right)=2[/math] 이다.
또한 [math]\sum_{k=1}^{n}P\left(n ,k \right) = {P}_{n}[/math]로 표기한다.
자연수의 분할에서는 다음 공식이 성립한다.
[math]P\left(n,2 \right)=\left[\frac{n}{2} \right][/math]
[math]P\left(n,3 \right)=\{\frac{{n}^{2}}{12}\} [/math][2]
단 여기서 [math]\left[ x \right][/math]는 [math]x[/math]를 넘지 않는 최대정수이고 [math]\{x\}[/math]는 [math]x[/math]를 반올림[3]한 것이다.
(3,2,2), (3,3,1)과 같이 서로가 서로의 'k 이상의 자연수 개수'를 나타내는 두 분할의 관계를 conjugate라고 한다. 즉 (3,2,2)에서는 1 이상인 자연수 개수가 3, 2 이상인 자연수 개수가 3, 3 이상인 자연수 개수가 1이므로 (3,2,2)의 conjugate partition이 (3,3,1)이 되는 것이다. 이는 파티션 개수대로 가로로 블록을 쌓고 세로로 블록 수를 세어서 새로운 파티션을 얻는 것과 같으므로, conjugate partition은 일대일 대응이다.
2.2 집합의 분할 (제2종 스털링 수)
원소가 [math]n[/math]개인 집합을 [math]r[/math]개의 공집합이 아니면서 서로소인 부분집합들의 합집합으로 나타내는 가짓수를 [math]S\left(n,r\right)[/math]로 표기한다.[1] 예를 들어 [math]\left\{1,2,3\right\}[/math]을 [math]2[/math]개의 부분집합들로 나누면 [math]\left\{1,2\right\}\cup\left\{3\right\}=\left\{1,3\right\}\cup\left\{2\right\}=\left\{2,3\right\}\cup\left\{1\right\}[/math]이므로 [math]S\left(3,2\right)=3[/math] 이다.
집합의 분할 [math]S\left(n, k\right)[/math]는 다음과 같은 공식이 있다.
[math]\displaystyle \ S\left(n, k\right) = {1\over k!}\sum_{r=0}^{k-1}\binom{k}{r}\left(-1\right)^r\left(k-r\right)^n [/math]
이 공식이 나오는 배경은 중복순열과 관련된다. 서로 다른 k개의 상자에 서로 다른 공 n개를 넣는 방법의 수는, 빈 상자가 있어도 되는 경우에는 [math] k^n [/math] 이고,빈 상자가 없어야 된다면 [math] S\left(n, k\right) \cdot k! [/math] 이다.
그런데 빈 상자가 없는 경우의 수는 중복순열로도 계산할 수 있는데, [math]k[/math]개의 상자에 [math]n[/math]개의 공을 넣고(빈 상자 있어도 됨), 이 중에서 임의의 한 상자가 빈 경우의 수 즉, [math]k-1[/math]개의 상자에 [math]n[/math]개의 공을 넣는 방법의 수 (빈 상자 있어도 됨) 를 빼자. 그런데 여기서 다시 임의의 두 상자가 빈 경우는 중복해서 빼버린 게 되니 그 경우의 수를 다시 더한다. 그런데 이러면 임의의 세 상자가 빈 경우는 중복해서 더해버린 게 되어 다시 뺀다 (...) 이렇게 임의의 [math]k-1[/math]개의 상자가 빈 경우의 수까지 계산하면 [4] 결국 [math] S\left(n, k\right) \cdot k! [/math] 과 같으므로, [math] k! [/math] 로 나누어주면 위 공식을 얻게 된다.