자연수의 분할과 P(n,3) 공식 증명

자연수의 분할 $p(n,k)$란?

자연수 $n$을 $k$개의 자연수로 분할하는 방법의 수를 $p(n,k)$ 라고 한다.

자연수의 분할에서 순서는 구별하지 않는데, 예를 들어

$$6=4+1+1=3+2+1=2+2+2$$이므로 $p(6.3)=3$이 된다.

공-상자 이론으로 설명해보면, $p(n,k)$는 구별되지 않는 $n$개의 공을 구별되지 않는 $k$개의 상자에 담을 때 빈 상자가 없도록 담는 경우의 수와 같다.

 

자연수의 분할 공식

자연수의 분할에는 많은 공식이 있다. 그 중 직접적으로 $p(n,k)$를 구하는 공식을 살펴보면, 다음과 같다.

$$p(n,1)=1$$ $$p(n,2)=\lfloor \frac{n}{2}\rfloor$$ $$p(n,3)=\left\{\frac{n^2}{12}\right\}$$ $$p(n,n-1)=1$$ $$p(n,n)=1$$

 

여기서 $p(n,2)$에서 괄호는 내림 기호이고, $p(n,3)$에서는 반올림 기호이다. 증명에서도 계속 이 기호로 쓸 것이다.

 

나머지 공식의 경우 조금만 생각해보면 쉽게 이해 할 수 있지만, $p(n,3)$ 공식은 그렇지 않다.

$p(n,2)$ 공식을 이용하여 $p(n,3)$ 공식을 증명해 보자.

 

p(n,3) 증명

자연수 $m$과 $0\le l<6$인 정수 $l$에 대해 임의의 자연수 $n$을 $n=6m+l$로 나타낼 수 있다.

이때 $1<k\le n$인 정수 $k$, $n$에 대하여,

$$p(n,1)+p(n,2)+\cdots +p(n,k)=p(n+k,k)$$ 가 성립한다는 사실이 알려져 있다.

(미리 k개의 상자에 하나씩 공을 넣어놓는다고 생각하면 성립한다는 걸 이해할 수 있다)

이를 이용하면,

$$p(6(m+1)+l,3)=p(6m+3+l,1)+p(6m+3+l,2)+p(6m+3+l,3)$$

이제 위에서 설명했던 $p(n,1)$과 $p(n,2)$ 공식으로 정리해보면,

$$\begin{array}{rl}p(6(m+1)+l,3)& =1+\lfloor \frac{6m+3+l}{2}\rfloor +p(6m+3+l,3)\\ & =1+3m+1+\lfloor \frac{1+l}{2}\rfloor +p(6m+3+l,3)\end{array}$$

가 성립한다.

또한 마찬가지로 생각해보면,

$$p(6m+3+l,3)=p(6m+l,1)+p(6m+l,2)+p(6m+l,3)=1+3m+\lfloor \frac{l}{2}\rfloor +p(6m+l,3)$$

가 성립한다. 이제 두 식을 더하면, 다음 점화식을 얻는다.

$$p(6(m+1)+l,3)=6m+3+\lfloor \frac{l}{2}\rfloor +\lfloor \frac{l+1}{2}\rfloor +p(6m+l,3)$$ 

이제 점화식을 풀면,

$$\begin{array}{rl}p(6m+l,3)& =p(6+l,3)+\sum _{k=1}^{m-1}(6k+3+\lfloor \frac{l}{2}\rfloor +\lfloor \frac{l+1}{2}\rfloor )\\ & =p(6+l,3)+(m-1)(3m+3+\lfloor \frac{l}{2}\rfloor +\lfloor \frac{l+1}{2}\rfloor )\end{array}$$

이 된다.

$n$을 6으로 나눈 나머지인 $l$에 따라 경우의 수를 나눠서 직접 계산해보면,

$$n=6m-3:p(n,3)=\frac{n^2}{12}+\frac{1}{4}$$

$$n=6m\pm 2:p(n,3)=\frac{n^2}{12}-\frac{1}{3}$$

$$n=6m\pm 1:p(n,3)=\frac{n^2}{12}-\frac{1}{12}$$

$$n=6m:p(n,3)=\frac{n^2}{12}$$

즉 $p(n,3)$은 모두 $\frac{n^2}{12}$를 반올림한 꼴임을 알 수 있다.

따라서 다음 식을 얻는다.  $$p(n,3)=\left\{\frac{n^2}{12}\right\}$$