집합의 분할과 자연수의 분할

다섯 명의 친구를 세 모둠으로 나누려 한다. 모둠에는 이름이 없고, 빈 모둠은 없어야 한다. 예를 들어 {가, 나}, {다, 라}, {마}처럼 나눌 수 있다. 이런 나누기는 모두 몇 가지일까? 한편 사람을 구별하지 않고 모둠의 인원수만 본다면 5를 \(2 + 2 + 1\), \(3 + 1 + 1\)처럼 세 자연수의 합으로 나타내는 방법만 남는다. 사람을 구별할 때와 구별하지 않을 때, 나누는 방법의 수는 어떻게 다를까?

1.4.1집합의 분할

원소가 \(n\)개인 집합을 공집합이 아닌 \(k\)개의 부분집합으로 나누되, 부분집합끼리는 겹치지 않고 합치면 원래 집합이 되도록 하는 것을 집합의 분할이라 한다. 그 방법의 수를 \(S(n, k)\)로 쓴다. 모둠에 이름이 없으므로 같은 원소들을 묶은 모둠의 순서는 따지지 않는다. 그래서 인원 구성별로 나누어 세고, 인원이 같은 모둠이 여러 개이면 그 모둠들끼리 자리를 바꾸는 수로 나누어야 한다.

\(S(n, k)\)의 점화식은 마지막 사람 한 명을 따로 생각해서 얻는다. 그 사람이 혼자 모둠을 이루면 나머지 \(n - 1\)명을 \(k - 1\)모둠으로 나누는 \(S(n - 1, k - 1)\)가지이다. 그렇지 않으면 나머지를 \(k\)모둠으로 먼저 나눈 뒤 그 사람이 \(k\)개의 모둠 가운데 하나에 들어가므로 \(k\,S(n - 1, k)\)가지이다. 이 점화식으로 \(S(5, 3) = S(4, 2) + 3S(4, 3) = 7 + 3\times6 = 25\)를 얻어 그림 1과 같다.¹

1.4.2점 그림을 뒤집으면

자연수의 분할은 점 그림으로 나타내면 성질이 잘 보인다. \(6 = 3 + 2 + 1\)을 첫 줄에 점 3개, 둘째 줄에 2개, 셋째 줄에 1개를 왼쪽 맞추어 찍어 나타낸다. 이 그림을 대각선에 대해 뒤집어 가로줄과 세로줄을 바꾸면 또 하나의 분할이 나온다. 원래 분할의 개수 \(k\)는 뒤집은 그림의 첫 줄 길이, 곧 가장 큰 수가 된다. 그래서 \(n\)을 정확히 \(k\)개로 나누는 분할과 가장 큰 수가 \(k\)인 분할은 하나씩 짝지어지고, 두 수는 같다.

1.4.3예제 풀이

인원 구성은 \(3 + 1 + 1\)과 \(2 + 2 + 1\)뿐이다. \(3 + 1 + 1\)은 세 명을 고르면 나머지 둘은 한 명씩 모둠이 되므로 \({}_5\mathrm{C}_3 = 10\)가지이다. \(2 + 2 + 1\)은 혼자 남을 한 명을 고르고 나머지 넷을 두 명씩 나누는데, 두 모둠은 이름이 없으므로 \(5\times{}_4\mathrm{C}_2/2! = 15\)가지이다. 합하면 \(S(5, 3) = 25\)이다.

모둠에 이름이 있으면 25가지의 나누기마다 세 모둠에 이름을 붙이는 \(3! = 6\)가지가 있으므로 \(150\)가지이다. 이것은 포함배제로 구한 \(3^5 - 3\times2^5 + 3\times1^5 = 243 - 96 + 3 = 150\)과 같다. 5의 분할은 \(5, 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1\)의 7가지이다. 즉 구별되는 대상을 이름 없는 묶음으로 나누는 것은 집합의 분할, 구별되지 않는 수를 나누는 것은 자연수의 분할이며, 무엇을 구별하는지에 따라 같은 나누기도 다르게 센다.

아래 탐구 카드에서 다섯 명을 세 모둠으로 나누는 방법을 직접 나열해 보고, 점 그림을 뒤집어 짝지어지는 분할을 찾아보자.

1. \(S(n, k)\)는 스코틀랜드의 스털링이 1730년에 다룬 수여서 제2종 스털링 수라 부른다. 자연수의 분할 수는 100만 되어도 1억 9천만 개를 넘는데, 인도의 라마누잔과 영국의 하디가 1918년 그 크기를 매우 정확히 어림하는 식을 찾았다.