자연수 \(r\)의 분할(partition)이란, 합하여 \(r\)이 되는 자연수들의 모임이다. 만일 \(n\)개의 자연수를 합하여 \(r\)을 만들었다면, '\(r\)이 \(n\)개의 부분(part)들로 분할되었다'라고 말한다. 예를 들어, \(5\)는 \(7\)개의 분할, \[ 5;\quad 4+1,\ 3+2;\quad 3+1+1,\ 2+2+1;\quad 2+1+1+1;\quad 1+1+1+1+1, \] 을 갖는다. \(5\)의 분할을 셀 때, 예를 들어 \(3+2\)와 \(2+3\)은 동일한 것으로 여긴다는 것에 유의하자. 또한 \(5\)를 한 개의 부분으로 분할하는 방법은 한 가지; \(5\)를 두 개의 부분으로 분할하는 방법은 두 가지; \(5\)를 세 개의 부분으로 분할하는 방법은 두 가지; \(5\)를 네 개의 부분으로 분할하는 방법은 한 가지; \(5\)를 다섯 개의 부분으로 분할하는 방법은 한 가지이다.
앞으로 자연수 \(r\)의 \(n\)개의 부분을 갖는 분할의 개수를 \[ \Pi(r, n) \] 로 나타내자. 그러면 \(\Pi(r, n)\)은 구별되지 않는 \(r\)개의 공을 구별되지 않는 \(n\)개의 상자에 담을 때, 빈상자가 없도록 담는 경우의 수와 같다. '상자에 공 담기'라는 이 유용한 아이디어를 앞으로도 종종 써먹을 것이다. 자연수 \(r\)의 모든 분할의 총 개수는 \(\Pi(r)\)로 나타내자. 그러면 \(\Pi(r)\)은 구별되지 않는 \(r\)개의 공을 구별되지 않는 \(r\)개의 상자에 담는 경우의 수와 같다. 또한 \[ \Pi(r)=\sum_{j=1}^{r}\Pi(r, j)=\Pi(r+r, r)=\Pi(2r, r) \] 이 성립하는데, 여기서 가운데의 등호가 성립하는 것은 구별되지 않는 \(r\)개의 상자에 이미 공이 하나씩 들어 있고, 추가로 \(r\)개의 공을 이들 상자에 넣는 것을 생각해보면 자명하다 할 수 있겠다.
\(\Pi(r, n)\)의 정의에 의해 \begin{align*} \Pi(r, n)&=0\quad\mbox{if \(n>r\)},\\ \Pi(r, r)&=\Pi(r, 1)=1,\\ \Pi(r, n)&=\sum_{k=1}^{n}\Pi(r-n, k)=\Pi(r-1, n-1)+\Pi(r-n, n) \end{align*} 이 성립함을 얻는데, 여기서 마지막 등식은 정확히 \(1\)개의 공만 들어 있는 상자가 있는 경우와 정확히 \(1\)개의 공만 들어 있는 상자가 없는 경우로 나누어 생각하여 얻을 수 있다.
위의 점화관계가 Pascal의 삼각형을 만드는 것만큼 극적이진 않더라도 다음 표1을 만드는데 유용하게 사용할 수 있다. 예를 들어 공식 \(\Pi(r, n)=\Pi(r-1, n-1)+\Pi(r-n, n)\)을 이용하여 \(\Pi(19, 5)+\Pi(14, 6)=70+20=\Pi(20, 9)\)를 계산할 수 있다. 표의 맨 아래쪽 행에 있는 \(90\)은 같은 열 위쪽에 있는 \(20\) 그리고 바로 위 왼쪽의 \(70\)을 합한 것으로 이해할 수 있다.
만일 \(\Pi(r, n)\)에 대한 '닫힌형태'의 예쁜 식을 찾고자 한다면, 지금까지 하지 않았던 다른 방식의 접근을 해야할 것이다.