자연수의 분할과 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)=\left\lfloor \frac{n}{2} \right\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\leq l <6$인 정수 $l$에 대해 임의의 자연수 $n$을 $n=6m+l$로 나타낼 수 있다.

이때 $1<k \leq 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{align} p(6(m+1)+l,3) &=1+ \left\lfloor \frac{6m+3+l}{2} \right\rfloor +p(6m+3+l,3)  \\[3pt] &= 1+3m+1+ \left\lfloor \frac{1+l}{2} \right\rfloor +p(6m+3+l,3) \end{align} $$

가 성립한다.

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

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

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

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

이제 점화식을 풀면,

$$ \begin{align} p(6m+l,3)&=p(6+l,3)+\sum_{k=1}^{m-1} \left(6k+3+\left\lfloor \frac{l}{2} \right\rfloor+\left\lfloor \frac{l+1}{2} \right\rfloor \right) \\[3pt] &= p(6+l,3)+(m-1) \left(3m+3+ \left\lfloor \frac{l}{2} \right\rfloor+\left\lfloor \frac{l+1}{2} \right\rfloor \right) \end{align} $$

이 된다.

$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\}$$