자연수의 분할이란?
숫자 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)+⋯+P(n,k−1)+P(n,k)P(n,1)=1,P(n,n)=1P(n,k)=P(n−1,k−1)+P(n−k,k)P(n,k)=P(n−k,1)+P(n−k,2)+⋯+P(n−k,k)