자연수의 분할

자연수의 분할이란?

숫자 5를 합으로 표현할 수 있는 모든 가지 수는 몇 가지가 나올까?

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

이렇듯, 주어진 자연수를 몇 개의 자연수의 합으로 나타내는 것을 자연수의 분할이라고 한다.

P(5, 1) = 1, [5]
P(5, 2) = 2, [4, 1], [3, 2]
P(5, 3) = 2, [3, 1, 1], [2, 2, 1]
P(5, 4) = 1, [2, 1, 1, 1]
P(5, 5) = 1, [1, 1, 1, 1, 1]

이런식으로 표현이 가능하다. 이러한 방법에서 살펴보아야 할 것은 P(n,k)의 의미일 것이다.

P(n, k) = 자연수 n을 k개의 자연수의 합으로 나타내는 방법의 수

여기서 사용되는 P가 Partition, 분할의 의미이다. 이러한 식으로 위의 예시를 성질으로 표현을 해보자.

P(n, k) = P(n, 1) + P(n, 2) + P(n, 3) + \cdots + P(n, k - 1) + P(n, k)

P(n, 1) = 1, P(n, n) = 1

P(n, k) = P(n -1, k-1) + P(n-k, k)

P(n, k) = P(n-k, 1) + P(n-k, 2) + \cdots + P(n-k, k)