자연수 분할

정수론에서 분할수(partition number)란, 어떤 양의 정수 n 을 그보다 작은 양의 정수들의 합으로 나타내는 방법의 수를 의미한다. n의 분할수는 일반적으로 p(n) 으로 표기한다. 단, p(0) = 1로 정의하며, n이 음의 정수일 때, p(n) = 0 로 정의한다.

예제

양의 정수 3을 생각해보자.

1. 3 = 3
2. 3 = 1 + 2
3. 3 = 1 + 1 + 1

으로 총 세가지의 경우가 있으므로, 3의 분할수는 p(3) = 3이 된다.

4일 때는,

1. 4 = 4
2. 4 = 3 + 1
3. 4 = 2 + 2
4. 4 = 2 + 1 + 1
5. 4 = 1 + 1 + 1 + 1

총 다섯가지이므로, 4의 분할수는 p(4) = 5가 된다.