직관 — 같은 구슬을 이름 없는 주머니에 나눈다
구별할 수 없는 구슬을 이름 없는 주머니에 나누어 담아 보자. 각 주머니에 든 개수만 남기면 어느 구슬이 들어갔는지는 중요하지 않다. 주머니 순서를 바꿔도 같은 나누기다.
구슬의 전체 개수는 나눌 자연수, 비어 있지 않은 주머니의 개수는 부분의 수다. 이 글의 분배는 가상 상황이다. 앞의 집합의 분할과 달리 여기서는 물건의 이름을 구별하지 않는다. 같은 물건을 똑같은 상자에 나누는 문제와 블록 크기의 모양을 정리하는 문제가 모두 이 수로 정리된다.
자연수의 분할은 양의 부분들의 순서 없는 합이다
자연수의 분할은 자연수 을 양의 정수들의 합으로 나타내되 더하는 순서만 다른 것은 같게 보는 것이다. 합에 쓰인 각 수를 부분이라 하고, 정확히 개 부분을 쓰는 방법 수를 로 쓴다. 같은 수가 여러 부분에 나타나는 것은 허용한다.
예를 들어 8을 세 부분으로 나누는 경우를 큰 부분부터 적으면 다음 다섯 가지다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 나눌 자연수 | integer being partitioned | 부분들의 합 | |
| 부분의 수 | number of parts | 양의 정수 항의 개수 | |
| 자연수의 분할 수 | integer partition count | 을 정확히 개 양의 부분으로 나누는 수 | |
| 부분 | parts | , 합은 |
큰 순서로 쓰는 것은 새 조건을 더한 것이 아니라 같은 분할을 한 번만 적는 방법이다. , , 은 하나의 분할이다. 여기서 는 순열 기호 와 다르다. 더 읽기의 Levin 교재는 '수 를 정확히 개 부분으로' 나누는 수를 로 써서 두 문자의 역할이 이 글과 반대다.
그림 1처럼 각 부분을 한 행으로 삼아 그 크기만큼 칸을 그리면 분할을 한눈에 읽을 수 있다. 교과서는 이를 분할의 그림이라 하고, 영문 자료는 영 다이어그램(Young diagram) 또는 페러스 그림(Ferrers diagram)이라 부른다. 행의 수가 부분의 수이고, 첫 행의 길이가 가장 큰 부분이다.
figures/eight_three_parts.py자연수의 분할 점화식은 1의 포함 여부로 증명한다
부분 1이 있는 경우와 모든 부분이 2 이상인 경우는 겹치지 않고 전체 분할을 나눈다. 각 경우를 더 작은 수의 분할과 일대일로 대응시키면
를 얻는다. 우선 정수 에서 두 대응을 확인하자.
부분 1이 있는 경우에는 1 하나를 없앤다. 합은 , 부분 수는 이 된다. 반대로 의 부분 분할에 1 하나를 더하면 원래 경우를 얻는다. 1이 여러 개 있어도 서로 구별하지 않으므로 ‘어느 1을 없앴는가’를 따로 곱하지 않는다.
모든 부분이 2 이상인 경우에는 각 부분에서 1씩 뺀다. 부분 수 는 유지되고 합은 가 되며, 각 부분은 여전히 양수다. 반대로 의 부분 분할에 부분마다 1씩 더하면 원래 경우를 복원한다. 따라서 이 경우의 수는 다.
figures/partition_reductions.py두 대응은 되돌릴 수 있어 누락과 중복이 없고, 합의 법칙으로 더하면 식 (2)가 성립한다. 그림 2의 두 사례가 일반 증명을 대신하는 것이 아니라, 위의 두 대응을 보여 준다. 분할의 그림으로 말하면 앞의 경우는 길이 1인 마지막 행을, 뒤의 경우는 첫 열 전체를 지운다.
자연수의 분할은 경계값을 정한 뒤 계산한다
양의 에서 이다. 원래 수 하나로 쓰거나 1을 개 쓰는 방법뿐이기 때문이다. 이면 양의 부분을 개 만들 수 없어 0이다.
계산 편의를 위해 을 빈 분할로 정한다. 양의 에 대해 이고, 양의 에 대해 이다. 이 경계 규약을 쓰면 식 (2)는 , 에서도 일관된다. 빈 분할 한 가지는 0을 양의 부분 하나로 쓰는 것과 다르다.
식 (1)을 점화식으로 확인하자. 7의 두 부분 분할은 , , 으로 세 가지이고, 5의 세 부분 분할은 , 로 두 가지다.
앞 항은 식 (1)에서 1을 포함한 세 경우에, 뒤 항은 모든 부분이 2 이상인 두 경우에 대응한다.
그림 3은 같은 계산을 까지 이어 놓은 표다. 한 칸의 값은 왼쪽 위 칸의 값과, 같은 열에서 행 위 칸의 값을 더한 것이다. 8행을 모두 더하면 로, 부분의 수를 정하지 않은 8의 분할 전체 수다.
figures/partition_table.py자연수를 두 부분으로 나누는 분할 수는 왜 절반의 정수 부분일까?
두 부분 에서 작은 부분 만 정하면 가 정해지기 때문이다. 조건 는 , 곧 이므로 는 1부터 이하의 가장 큰 정수까지 고를 수 있다.
실수 이하인 가장 큰 정수를 로 쓰면 다음과 같다.
8이면 로 이고, 7이면 으로 이다. 식 (3)에서 쓴 3과 같다.
자연수의 분할은 상자의 이름과 빈 곳 조건을 먼저 정한다
같은 구슬 8개를 이름 없는 세 상자에 빈 곳 없이 넣으면 각 상자의 양의 개수만 남으므로 가지다. 빈 상자를 허용하면 사용한 상자 수가 1, 2, 3 중 하나가 된다.
여기서 는 , , , 다. 상자에 X, Y, Z 이름이 있다면 같은 분할도 어느 상자에 어느 부분을 넣는지에 따라 달라진다. 그림 4처럼 세 부분이 서로 다른 은 가지 순서로 놓이고, 같은 부분이 둘인 은 3가지다.
figures/ordered_counts.py21은 중복조합으로도 얻는다. 상자 X, Y, Z를 세 종류로 보면, 세 종류에서 8개를 고르되 어느 종류도 빠지지 않게 하는 수는 먼저 하나씩 고른 뒤 남은 5개를 중복을 허용해 고르는 수 다. 상자 문제는 물건과 상자의 구별 여부로 네 가지로 나뉜다. 8개를 세 상자에 빈 곳 없이 넣는 경우를 비교하면 다음과 같다.
| 물건 | 상자 | 세는 방법 | 수 |
|---|---|---|---|
| 서로 다름 | 이름 있음 | 5796 | |
| 서로 다름 | 이름 없음 | 집합의 분할 | 966 |
| 같음 | 이름 있음 | 중복조합 | 21 |
| 같음 | 이름 없음 | 자연수의 분할 | 5 |
은 집합의 분할 수의 점화식으로 이다. 물건이 같아지면 수가 크게 줄고, 상자 이름을 지우면 다시 줄어든다.
켤레 분할은 부분의 수와 가장 큰 부분을 맞바꾼다
분할의 그림에서 각 열의 칸 수를 차례로 읽으면 같은 수의 새 분할이 생긴다. 이를 원래 분할의 켤레 분할(conjugate partition)이라 한다. 행과 열을 맞바꾼 것이므로 칸의 총수는 그대로다.
의 그림은 첫째와 둘째 열에 3칸씩, 셋째와 넷째 열에 1칸씩 있어 켤레 분할은 이다. 그림 5처럼 원래의 부분 수 3이 켤레의 가장 큰 부분이 되고, 원래의 가장 큰 부분 4가 켤레의 부분 수가 된다.
figures/conjugate_partition.py켤레를 한 번 더 취하면 원래 분할로 돌아오므로 이 대응은 일대일대응이다. 따라서 는 가장 큰 부분이 정확히 인 의 분할 수와 같다. 또 부분이 3개 이하인 8의 분할 수와 가장 큰 부분이 3 이하인 8의 분할 수는 같아서, 식 (5)의 10은 뒤의 수이기도 하다.
자연수의 분할은 양의 부분들의 합에서 순서를 구별하지 않는다. 정수 에서 부분 1 하나를 지우는 경우와 모든 부분에서 1씩 빼는 경우를 나누면 가 된다.
자연수의 분할에 0을 하나의 부분으로 넣어도 되나요?
아니다. 자연수의 분할에서 부분은 양의 정수다. 8을 세 부분으로 나눌 때 은 포함하지 않으며, 빈 상자를 허용한 분배에서는 사용한 양의 부분 수를 1부터 따로 센다.
자연수의 분할에서 같은 수가 반복되면 안 되나요?
반복을 허용한다. 와 도 8의 세 부분 분할이다. ‘서로 다른 부분으로만’이라는 별도 조건을 붙이면 8의 세 부분 분할은 과 의 2가지만 남는다.
자연수의 분할과 집합의 분할은 왜 수가 다른가요?
자연수의 분할은 부분의 크기만 보지만 집합의 분할은 각 원소의 이름도 구별하기 때문이다. 4를 두 양의 부분으로 나누면 과 의 2가지지만, 서로 다른 네 원소를 두 블록으로 나누면 7가지다.
자연수의 분할의 흔한 오해
- 1이 여러 개면 제거할 1의 개수만큼 곱한다 — 에서 어느 1을 지워도 같은 이다. 구별하지 않는 1을 다시 이름 붙여 중복을 만들면 안 된다.
- 점화식의 뒤 항에서도 부분 수가 하나 줄어든다 — 에서 각각 1을 빼면 로 여전히 세 부분이다. 줄어드는 것은 합 3이며 부분 수가 아니다.
- 이름 있는 상자의 수는 분할 수에 상자 수의 계승을 곱하면 된다 — 같은 구슬 8개와 세 상자에서 이지만 실제는 식 (6)의 21이다. 같은 부분이 있는 분할은 순서를 바꿔 쓰는 방법이 3가지뿐이다.
직접 해보기
- 의 모든 분할을 적고 점화식으로도 확인하라.
- 을 구하라. 와 은 직접 나열하여 계산하라.
- 같은 구슬 6개를 이름 없는 세 상자에 넣는다. 빈 곳을 금지할 때와 허용할 때의 수를 각각 구하라.
- 11을 세 부분으로 나누되 모든 부분이 2 이상인 분할을 모두 적어라. 그 개수는 식 (2)의 어느 항과 같은가?
- 분할 의 켤레 분할을 구하고, 부분의 수와 가장 큰 부분이 어떻게 바뀌는지 적어라.
답과 풀이
- , , , 의 4가지다. 와 같다.
- 이고, 6의 세 부분은 , , 라 이다. 따라서 이다.
- 빈 곳을 금지하면 가지다. 허용하면 가지다.
- , , , , 의 5가지다. 각 부분에서 1씩 빼면 8의 세 부분 분할이 되므로 , 일 때의 뒤 항 와 같다.
- 그림의 열 길이는 차례로 3, 2, 2, 1, 1이므로 켤레 분할은 이다. 부분의 수 3은 켤레의 가장 큰 부분 3이 되고, 가장 큰 부분 5는 켤레의 부분 수 5가 된다.
더 읽기
- 우리교과서 2022 개정 고등학교 이산 수학 — 이준열 외, 인쇄30–34쪽. 자연수의 분할, 상자 문제, 분할의 그림, 1 포함 여부의 점화식 유도를 확인했다.
- More Discrete Mathematics — Integer Partitions — Oscar Levin. 큰 부분부터 적는 정의, 영 다이어그램과 켤레 분할을 읽었다. 생성함수 등 뒤의 확장 주제는 이 글의 선수로 삼지 않는다.
영상 노트
- 00:00 같은 구슬과 이름 없는 주머니로 집합의 분할과 구별한다.
- 00:35 그림 1의 분할의 그림에서 식 (1)의 다섯 분할을 읽는다.
- 01:15 그림 2의 지우기와 되돌리기로 식 (2)를 증명한다.
- 02:15 경계값과 식 (3)의 두 항을 확인하고 그림 3의 표를 채운다.
- 02:55 작은 부분만 정해 식 (4)의 두 부분 분할 수를 센다.
- 03:25 빈 상자를 허용한 식 (5), 이름 있는 상자의 식 (6)과 그림 4, 네 가지 분배 표를 비교한다.
- 04:20 그림 5에서 행과 열을 바꿔 켤레 분할을 만들고 새 연습을 푼다.
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 분할 수 표와 전체 분할 수, 두 부분 분할의 일반식, 켤레 분할, 이름 있는 상자의 순서쌍 그림과 중복조합 대응·네 가지 분배 표, Levin 표기 설명 정정, 질문·연습 보강 (에이전트 수정, 그림 2→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림