5.1 자연수의 분할

자연수 분할은 일종의 '블럭 놀이'로 생각할 수 있다.

$n$개의 정사각형 모양의  납작한 블럭들을 서로 변끼리 서로 연결하여 어떤 모양을 만든다. 이때 그 모양에 따라 자연수 $n$의 분할들이 만들어진다. 이러한 블럭 놀이를 통해 얻을 수 있는 하니의 원리가 있다. 

"자연수 '$n$을 $k$이하의 자연수로 분할하는 방법의 수'는 '자연수 $n$을 $k$개 이하의 자연수로 분할하는 방법의 수'와 같다." 

 

위의 문장에서 $n$을 $k$이하의 자연수로 분할하는 방법의 수와 자연수 $n$을 $k$개 이하의 자연수로 분할하는 방법의 수는 분명 다른 문장이다. 

다음 그림을 통해 위의 사실을 이해할 수 있겠는가?

7을 3이하의 자연수로 분할하는 방법은 다음과 같다. 

   7 = 3+3+1 = 3+2+2
      = 3+2+1+1 = 2+2+2+1 
      = 3+1+1+1+1 = 2+2+1+1+1 
      = 2+1+1+1+1+1
      = 1+1+1+1+1+1+1

자연수 6을 순서를 생각하지 않고 3개의 자연수의 합으로 나타내면 
   4+1+1, 3+2+1, 2+2+2
이다. 이때 순서를 생각하지 않고 나타낸다는 것은 이를테면 
   4+1+1, 1+4+1, 1+1+4
는 모두 같은 것으로 본다는 뜻이다. 편의상, 크기 순으로 정리하여 나타내는 것이 여러모로 좋다. 이와 같이 어떤 자연수를 몇 개의 자연수의 합으로 나타내는 것을 '자연수의 분할'이라고 한다. 

위의 내용을 정리하면 다음과 같다. 

---

자연수의 분할

자연수 $n$를 $k$개의 자연수로 $n_1, n_2,\cdots, n_k$의 합으로 
   $n = n_1 + n_2 + \cdots + n_k$ (단, $n_1 \geq n_2 \geq n_3 \geq \cdots \geq n_k$)
와 같이 나타내는 것을 '자연수의 분할'이라고 한다. 자연수 $n$을 $k$개의 자연수로 분할하는 방법의 수를
   $N(n,k)$

와 같이 나타내자. 이때, 자연수 $n$을 분할하는 모든 방법의 수 $p(n)$은 
   $p(n) = N(n,1)+N(n,2)+\cdots+N(n,n)$
이다. 

 

$N(n,k)$는 서로 같은 공을 서로 같은 $k$개의 상자에 빈 상자가 없도록 넣는 방법의 수와 같다.

---

두 자연수 $n,k(1<k<n)$에 대하여 다음 규칙이 성립한다.

⑴ $N(n,k) = N(n-1,k-1) + N(n-k,k)$

⑵ $N(n,k) = N(n-k,1)+N(n-k,2)+\cdots+N(n-k,k)$

이것을 증명해 보자.
(1) ; 공 $1$개만 넣은 상자가 있는 경우와 공 $1$개만 넣은 상자가 없는 경우로 나누어 생각할 수 있다.

 

공 $1$개만 넣은 상자가 있는 경우의 수는 $k$개의 상자 중에서 공 $1$개만 넣은 상자 $1$개 를 제외한 나머지 $(k-1)$의 상자에  남은 $(n-1)$개의 공을 빈 상자가 없도록 넣는 경우의 수

   $N(n-1,k-1)$

과 같다. 

 

공 1개만 넣은 상자가 없는 경우의 수는 먼저 $k$개의 상자에 각각 공을 $1$개씩 넣은 다음, 남은 $(n-k)$개의 공을 $k$개의 상자에 빠짐없이 넣는 경우의 수
   $N(n-k, k)$
와 같다. 따라서 '합의 법칙' 에 의해  (1)은 성립한다. 

 

(2)  ;  좌변의 $N(n,k)$는 서로 같은 공을 서로 같은 $k$개의 상자에 빈 상자가 없도록 넣는 방법의 수이다. 이것을 우변의 관점에서 보자. 

$k$개의 상자에 빈상자가 없도록 담아야 하므로 먼저 $k$개의 공을 각각 $1$개씩 담은 다음, 남은 공 $(n-k)$개를 상자 $1$개에 모두 담는 경우, 상자 $2$개에 빠짐없이 담는경우, $\cdots$, 상자 $k$개에 빠짐없이 담는 경우로 나누어 생각하면 '합의 법칙'에 의해 (2)가 성립한다.