확률·통계자연수의 분할#341

자연수의 분할

Integer Partitions

자연수의 분할은 자연수를 양의 정수들의 순서 없는 합으로 나타내는 것이다. 부분이 같은 크기여도 반복을 허용한다. 1의 포함 여부로 점화식을 증명하고, 분할의 그림과 켤레 분할, 이름 없는 상자와 이름 있는 상자의 분배를 비교한다.

읽는 시간
약 7분
선수 개념
집합의 분할

직관 — 같은 구슬을 이름 없는 주머니에 나눈다

직관

구별할 수 없는 구슬을 이름 없는 주머니에 나누어 담아 보자. 각 주머니에 든 개수만 남기면 어느 구슬이 들어갔는지는 중요하지 않다. 주머니 순서를 바꿔도 같은 나누기다.

구슬의 전체 개수는 나눌 자연수, 비어 있지 않은 주머니의 개수는 부분의 수다. 이 글의 분배는 가상 상황이다. 앞의 집합의 분할과 달리 여기서는 물건의 이름을 구별하지 않는다. 같은 물건을 똑같은 상자에 나누는 문제와 블록 크기의 모양을 정리하는 문제가 모두 이 수로 정리된다.

자연수의 분할은 양의 부분들의 순서 없는 합이다

자연수의 분할은 자연수 nn을 양의 정수들의 합으로 나타내되 더하는 순서만 다른 것은 같게 보는 것이다. 합에 쓰인 각 수를 부분이라 하고, 정확히 kk개 부분을 쓰는 방법 수를 P(n,k)P(n,k)로 쓴다. 같은 수가 여러 부분에 나타나는 것은 허용한다.

예를 들어 8을 세 부분으로 나누는 경우를 큰 부분부터 적으면 다음 다섯 가지다.

8=6+1+1=5+2+1=4+3+18=4+2+2=3+3+2,P(8,3)=5.(1)\begin{gathered} 8=6+1+1=5+2+1=4+3+1\\ \phantom{8}=4+2+2=3+3+2,\qquad P(8,3)=5. \end{gathered} \tag{1}
정의
기호이름원어뜻
nn나눌 자연수integer being partitioned부분들의 합
kk부분의 수number of parts양의 정수 항의 개수
P(n,k)P(n,k)자연수의 분할 수integer partition countnn을 정확히 kk개 양의 부분으로 나누는 수
a1,…,aka_1,\ldots,a_k부분partsa1≥⋯≥ak≥1a_1\ge\cdots\ge a_k\ge1, 합은 nn

큰 순서로 쓰는 것은 새 조건을 더한 것이 아니라 같은 분할을 한 번만 적는 방법이다. 6+1+16+1+1, 1+6+11+6+1, 1+1+61+1+6은 하나의 분할이다. 여기서 P(n,k)P(n,k)는 순열 기호 nPk{}_nP_k와 다르다. 더 읽기의 Levin 교재는 '수 kk를 정확히 nn개 부분으로' 나누는 수를 pn(k)p_n(k)로 써서 두 문자의 역할이 이 글과 반대다.

그림 1처럼 각 부분을 한 행으로 삼아 그 크기만큼 칸을 그리면 분할을 한눈에 읽을 수 있다. 교과서는 이를 분할의 그림이라 하고, 영문 자료는 영 다이어그램(Young diagram) 또는 페러스 그림(Ferrers diagram)이라 부른다. 행의 수가 부분의 수이고, 첫 행의 길이가 가장 큰 부분이다.

8의 세 부분 분할 다섯 가지를 분할의 그림으로 나타냈다. 각 묶음의 칸 수 합은 8이고 행 수는 3이며, 크기 1인 부분의 칸을 강조했다. 같은 행 길이가 반복되어도 하나의 분할로 허용한다.
그림 1 8의 세 부분 분할 다섯 가지를 분할의 그림으로 나타냈다. 각 묶음의 칸 수 합은 8이고 행 수는 3이며, 크기 1인 부분의 칸을 강조했다. 같은 행 길이가 반복되어도 하나의 분할로 허용한다. figures/eight_three_parts.py

자연수의 분할 점화식은 1의 포함 여부로 증명한다

부분 1이 있는 경우와 모든 부분이 2 이상인 경우는 겹치지 않고 전체 분할을 나눈다. 각 경우를 더 작은 수의 분할과 일대일로 대응시키면

P(n,k)=P(n−1,k−1)+P(n−k,k)(2)P(n,k)=P(n-1,k-1)+P(n-k,k) \tag{2}

를 얻는다. 우선 정수 n≥k≥2n\ge k\ge2에서 두 대응을 확인하자.

부분 1이 있는 경우에는 1 하나를 없앤다. 합은 n−1n-1, 부분 수는 k−1k-1이 된다. 반대로 n−1n-1의 k−1k-1부분 분할에 1 하나를 더하면 원래 경우를 얻는다. 1이 여러 개 있어도 서로 구별하지 않으므로 ‘어느 1을 없앴는가’를 따로 곱하지 않는다.

모든 부분이 2 이상인 경우에는 각 부분에서 1씩 뺀다. 부분 수 kk는 유지되고 합은 n−kn-k가 되며, 각 부분은 여전히 양수다. 반대로 n−kn-k의 kk부분 분할에 부분마다 1씩 더하면 원래 경우를 복원한다. 따라서 이 경우의 수는 P(n−k,k)P(n-k,k)다.

위는 8의 분할 (6,1,1)에서 맨 아래 1 하나를 지워 (6,1)을 얻는 대응이다. 아래는 (4,2,2)의 각 행에서 첫 칸 하나씩을 지워 (3,1,1)을 얻는 대응이다. 강조한 칸만 없애며 두 경우에서 부분 수 변화가 다르다.
그림 2 위는 8의 분할 (6,1,1)에서 맨 아래 1 하나를 지워 (6,1)을 얻는 대응이다. 아래는 (4,2,2)의 각 행에서 첫 칸 하나씩을 지워 (3,1,1)을 얻는 대응이다. 강조한 칸만 없애며 두 경우에서 부분 수 변화가 다르다. figures/partition_reductions.py

두 대응은 되돌릴 수 있어 누락과 중복이 없고, 합의 법칙으로 더하면 식 (2)가 성립한다. 그림 2의 두 사례가 일반 증명을 대신하는 것이 아니라, 위의 두 대응을 보여 준다. 분할의 그림으로 말하면 앞의 경우는 길이 1인 마지막 행을, 뒤의 경우는 첫 열 전체를 지운다.

자연수의 분할은 경계값을 정한 뒤 계산한다

양의 nn에서 P(n,1)=P(n,n)=1P(n,1)=P(n,n)=1이다. 원래 수 하나로 쓰거나 1을 nn개 쓰는 방법뿐이기 때문이다. k>nk>n이면 양의 부분을 kk개 만들 수 없어 0이다.

계산 편의를 위해 P(0,0)=1P(0,0)=1을 빈 분할로 정한다. 양의 nn에 대해 P(n,0)=0P(n,0)=0이고, 양의 kk에 대해 P(0,k)=0P(0,k)=0이다. 이 경계 규약을 쓰면 식 (2)는 n≥1n\ge1, 1≤k≤n1\le k\le n에서도 일관된다. 빈 분할 한 가지는 0을 양의 부분 하나로 쓰는 것과 다르다.

식 (1)을 점화식으로 확인하자. 7의 두 부분 분할은 6+16+1, 5+25+2, 4+34+3으로 세 가지이고, 5의 세 부분 분할은 3+1+13+1+1, 2+2+12+2+1로 두 가지다.

P(8,3)=P(7,2)+P(5,3)=3+2=5.(3)P(8,3)=P(7,2)+P(5,3)=3+2=5. \tag{3}

앞 항은 식 (1)에서 1을 포함한 세 경우에, 뒤 항은 모든 부분이 2 이상인 두 경우에 대응한다.

그림 3은 같은 계산을 n=8n=8까지 이어 놓은 표다. 한 칸의 값은 왼쪽 위 칸의 값과, 같은 열에서 kk행 위 칸의 값을 더한 것이다. 8행을 모두 더하면 1+4+5+5+3+2+1+1=221+4+5+5+3+2+1+1=22로, 부분의 수를 정하지 않은 8의 분할 전체 수다.

식 (2)로 채운 자연수의 분할 수 P(n,k)의 표(1≤ k≤ n≤8). 화살표는 P(8,3)=5를 왼쪽 위 칸 P(7,2)=3과 세 행 위 칸 P(5,3)=2의 합으로 얻는 과정이다.
그림 3 식 (2)로 채운 자연수의 분할 수 P(n,k)P(n,k)의 표(1≤k≤n≤81\le k\le n\le8). 화살표는 P(8,3)=5P(8,3)=5를 왼쪽 위 칸 P(7,2)=3P(7,2)=3과 세 행 위 칸 P(5,3)=2P(5,3)=2의 합으로 얻는 과정이다. figures/partition_table.py

자연수를 두 부분으로 나누는 분할 수는 왜 절반의 정수 부분일까?

두 부분 a≥b≥1a\ge b\ge1에서 작은 부분 bb만 정하면 a=n−ba=n-b가 정해지기 때문이다. 조건 a≥ba\ge b는 n−b≥bn-b\ge b, 곧 b≤n/2b\le n/2이므로 bb는 1부터 n/2n/2 이하의 가장 큰 정수까지 고를 수 있다.

실수 xx 이하인 가장 큰 정수를 ⌊x⌋\lfloor x\rfloor로 쓰면 다음과 같다.

P(n,2)=⌊n2⌋.(4)P(n,2)=\left\lfloor\frac{n}{2}\right\rfloor. \tag{4}

8이면 b=1,2,3,4b=1,2,3,4로 P(8,2)=4P(8,2)=4이고, 7이면 b=1,2,3b=1,2,3으로 P(7,2)=3P(7,2)=3이다. 식 (3)에서 쓴 3과 같다.

자연수의 분할은 상자의 이름과 빈 곳 조건을 먼저 정한다

같은 구슬 8개를 이름 없는 세 상자에 빈 곳 없이 넣으면 각 상자의 양의 개수만 남으므로 P(8,3)=5P(8,3)=5가지다. 빈 상자를 허용하면 사용한 상자 수가 1, 2, 3 중 하나가 된다.

P(8,1)+P(8,2)+P(8,3)=1+4+5=10.(5)P(8,1)+P(8,2)+P(8,3)=1+4+5=10. \tag{5}

여기서 P(8,2)=4P(8,2)=4는 7+17+1, 6+26+2, 5+35+3, 4+44+4다. 상자에 X, Y, Z 이름이 있다면 같은 분할도 어느 상자에 어느 부분을 넣는지에 따라 달라진다. 그림 4처럼 세 부분이 서로 다른 5+2+15+2+1은 3!=63!=6가지 순서로 놓이고, 같은 부분이 둘인 6+1+16+1+1은 3가지다.

3+6+6+3+3=21=7C2.(6)3+6+6+3+3=21={}_7C_2. \tag{6}
8의 세 부분 분할 다섯 가지를 이름 있는 세 상자에 넣는 방법. 열 하나가 분할 하나이고, 칸 안의 세 수는 상자 X, Y, Z에 든 구슬 수다. 예컨대 6+1+1은 (6,1,1), (1,6,1), (1,1,6)의 3칸이다. 부분이 모두 다른 분할은 6칸, 같은 부분이 있는 분할은 3칸이라 합은 21이다.
그림 4 8의 세 부분 분할 다섯 가지를 이름 있는 세 상자에 넣는 방법. 열 하나가 분할 하나이고, 칸 안의 세 수는 상자 X, Y, Z에 든 구슬 수다. 예컨대 6+1+1은 (6,1,1), (1,6,1), (1,1,6)의 3칸이다. 부분이 모두 다른 분할은 6칸, 같은 부분이 있는 분할은 3칸이라 합은 21이다. figures/ordered_counts.py

21은 중복조합으로도 얻는다. 상자 X, Y, Z를 세 종류로 보면, 세 종류에서 8개를 고르되 어느 종류도 빠지지 않게 하는 수는 먼저 하나씩 고른 뒤 남은 5개를 중복을 허용해 고르는 수 3H5=7C2{}_3H_5={}_7C_2다. 상자 문제는 물건과 상자의 구별 여부로 네 가지로 나뉜다. 8개를 세 상자에 빈 곳 없이 넣는 경우를 비교하면 다음과 같다.

물건상자세는 방법수
서로 다름이름 있음3!×S(8,3)3!\times S(8,3)5796
서로 다름이름 없음집합의 분할 S(8,3)S(8,3)966
같음이름 있음중복조합 3H5=7C2{}_3H_5={}_7C_221
같음이름 없음자연수의 분할 P(8,3)P(8,3)5

S(8,3)S(8,3)은 집합의 분할 수의 점화식으로 S(7,2)+3S(7,3)=63+3×301=966S(7,2)+3S(7,3)=63+3\times301=966이다. 물건이 같아지면 수가 크게 줄고, 상자 이름을 지우면 다시 줄어든다.

켤레 분할은 부분의 수와 가장 큰 부분을 맞바꾼다

분할의 그림에서 각 열의 칸 수를 차례로 읽으면 같은 수의 새 분할이 생긴다. 이를 원래 분할의 켤레 분할(conjugate partition)이라 한다. 행과 열을 맞바꾼 것이므로 칸의 총수는 그대로다.

(4,2,2)(4,2,2)의 그림은 첫째와 둘째 열에 3칸씩, 셋째와 넷째 열에 1칸씩 있어 켤레 분할은 (3,3,1,1)(3,3,1,1)이다. 그림 5처럼 원래의 부분 수 3이 켤레의 가장 큰 부분이 되고, 원래의 가장 큰 부분 4가 켤레의 부분 수가 된다.

분할 4+2+2의 그림에서 행과 열을 바꾸면 켤레 분할 3+3+1+1이 된다. 강조한 칸처럼 원래 그림의 첫 열이 켤레의 첫 행이 된다.
그림 5 분할 4+2+2의 그림에서 행과 열을 바꾸면 켤레 분할 3+3+1+1이 된다. 강조한 칸처럼 원래 그림의 첫 열이 켤레의 첫 행이 된다. figures/conjugate_partition.py

켤레를 한 번 더 취하면 원래 분할로 돌아오므로 이 대응은 일대일대응이다. 따라서 P(n,k)P(n,k)는 가장 큰 부분이 정확히 kk인 nn의 분할 수와 같다. 또 부분이 3개 이하인 8의 분할 수와 가장 큰 부분이 3 이하인 8의 분할 수는 같아서, 식 (5)의 10은 뒤의 수이기도 하다.

핵심

자연수의 분할은 양의 부분들의 합에서 순서를 구별하지 않는다. 정수 n≥k≥1n\ge k\ge1에서 부분 1 하나를 지우는 경우와 모든 부분에서 1씩 빼는 경우를 나누면 P(n,k)=P(n−1,k−1)+P(n−k,k)P(n,k)=P(n-1,k-1)+P(n-k,k)가 된다.

자연수의 분할에 0을 하나의 부분으로 넣어도 되나요?

아니다. 자연수의 분할에서 부분은 양의 정수다. 8을 세 부분으로 나눌 때 8+0+08+0+0은 포함하지 않으며, 빈 상자를 허용한 분배에서는 사용한 양의 부분 수를 1부터 따로 센다.

자연수의 분할에서 같은 수가 반복되면 안 되나요?

반복을 허용한다. 4+2+24+2+2와 3+3+23+3+2도 8의 세 부분 분할이다. ‘서로 다른 부분으로만’이라는 별도 조건을 붙이면 8의 세 부분 분할은 5+2+15+2+1과 4+3+14+3+1의 2가지만 남는다.

자연수의 분할과 집합의 분할은 왜 수가 다른가요?

자연수의 분할은 부분의 크기만 보지만 집합의 분할은 각 원소의 이름도 구별하기 때문이다. 4를 두 양의 부분으로 나누면 (3,1)(3,1)과 (2,2)(2,2)의 2가지지만, 서로 다른 네 원소를 두 블록으로 나누면 7가지다.

자연수의 분할의 흔한 오해

  • 1이 여러 개면 제거할 1의 개수만큼 곱한다 — (6,1,1)(6,1,1)에서 어느 1을 지워도 같은 (6,1)(6,1)이다. 구별하지 않는 1을 다시 이름 붙여 중복을 만들면 안 된다.
  • 점화식의 뒤 항에서도 부분 수가 하나 줄어든다 — (4,2,2)(4,2,2)에서 각각 1을 빼면 (3,1,1)(3,1,1)로 여전히 세 부분이다. 줄어드는 것은 합 3이며 부분 수가 아니다.
  • 이름 있는 상자의 수는 분할 수에 상자 수의 계승을 곱하면 된다 — 같은 구슬 8개와 세 상자에서 5×3!=305\times3!=30이지만 실제는 식 (6)의 21이다. 같은 부분이 있는 분할은 순서를 바꿔 쓰는 방법이 3가지뿐이다.

직접 해보기

  1. P(7,3)P(7,3)의 모든 분할을 적고 점화식으로도 확인하라.
  2. P(9,3)P(9,3)을 구하라. P(8,2)P(8,2)와 P(6,3)P(6,3)은 직접 나열하여 계산하라.
  3. 같은 구슬 6개를 이름 없는 세 상자에 넣는다. 빈 곳을 금지할 때와 허용할 때의 수를 각각 구하라.
  4. 11을 세 부분으로 나누되 모든 부분이 2 이상인 분할을 모두 적어라. 그 개수는 식 (2)의 어느 항과 같은가?
  5. 분할 (5,3,1)(5,3,1)의 켤레 분할을 구하고, 부분의 수와 가장 큰 부분이 어떻게 바뀌는지 적어라.
답과 풀이
  1. (5,1,1)(5,1,1), (4,2,1)(4,2,1), (3,3,1)(3,3,1), (3,2,2)(3,2,2)의 4가지다. P(6,2)+P(4,3)=3+1=4P(6,2)+P(4,3)=3+1=4와 같다.
  2. P(8,2)=4P(8,2)=4이고, 6의 세 부분은 (4,1,1)(4,1,1), (3,2,1)(3,2,1), (2,2,2)(2,2,2)라 P(6,3)=3P(6,3)=3이다. 따라서 P(9,3)=4+3=7P(9,3)=4+3=7이다.
  3. 빈 곳을 금지하면 P(6,3)=3P(6,3)=3가지다. 허용하면 P(6,1)+P(6,2)+P(6,3)=1+3+3=7P(6,1)+P(6,2)+P(6,3)=1+3+3=7가지다.
  4. (7,2,2)(7,2,2), (6,3,2)(6,3,2), (5,4,2)(5,4,2), (5,3,3)(5,3,3), (4,4,3)(4,4,3)의 5가지다. 각 부분에서 1씩 빼면 8의 세 부분 분할이 되므로 n=11n=11, k=3k=3일 때의 뒤 항 P(11−3,3)=P(8,3)=5P(11-3,3)=P(8,3)=5와 같다.
  5. 그림의 열 길이는 차례로 3, 2, 2, 1, 1이므로 켤레 분할은 (3,2,2,1,1)(3,2,2,1,1)이다. 부분의 수 3은 켤레의 가장 큰 부분 3이 되고, 가장 큰 부분 5는 켤레의 부분 수 5가 된다.

더 읽기

영상 노트

영상 노트
  • 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에서 행과 열을 바꿔 켤레 분할을 만들고 새 연습을 푼다.

지도에서의 위치

조합확률·통계집합의 분할확률·통계자연수의 분할지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 분할 수 표와 전체 분할 수, 두 부분 분할의 일반식, 켤레 분할, 이름 있는 상자의 순서쌍 그림과 중복조합 대응·네 가지 분배 표, Levin 표기 설명 정정, 질문·연습 보강 (에이전트 수정, 그림 2→5)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림