자연수의 분할

원문 보기: https://dawoum.duckdns.org/wiki/자연수의_분할

Main article: Partition (number theory)

집합의 분할은 서로 다른 원소를 몇 개의 부분으로 분할하는 경우의 수에 대한 내용이었습니다. 또한, 분배는 서로 다른 \(n\)개를 \(k\)개로 분할해서 서로 다른 \(n\)명에게 나누어주는 응용이었습니다. 만약 서로 같은 원소가 여러 개 있을 때, 이것을 분할해서 서로 같은 투명 상자(백)에 담는 경우의 수는 몇 개일까요?

서로 같은 원소는 결국 개수가 몇 개인지로 구별을 합니다. 즉, 서로 같은 원소 \(n\)개를 \(k\)개로 나누는 것은 자연수 \(n\)을 \(k\)개의 합으로 분할하는 경우와 동치입니다. 이런 응용들은 지칭해서 자연수의 분할이라고 말합니다.

집합의 분할에서는 분할하지 않는 것은 다루지 않았지만, 여기서는 분할하지 않는 것도 경우의 수에 포함합니다. 숫자 4를 분할해 보겠습니다.

\(\quad\)1개로 분할: 4

\(\quad\)2개로 분할: 3 + 1,

\(\quad\)2개로 분할: 2 + 2

\(\quad\)3개로 분할: 2 + 1 + 1

\(\quad\)4개로 분할: 1 + 1 + 1 + 1

이들 경우에서 1 + 3은 3 + 1과 같은 경우인데, 왜냐하면 분할에서 순서는 중요하지 않기 때문입니다. 단지 표기법을 더하기 기호를 이용할 뿐입니다. 어떤 경우에는 다음과 같이 튜플을 사용해서 나타내기도 합니다.

\(\quad\)(4)

\(\quad\)(3,1)

\(\quad\)(2,2)

\(\quad\)(2,1,1)

\(\quad\)(1,1,1,1)

위의 결과는 자연수 4를 1개로 분할 1가지, \(p_1(4)=1\), 2개로 분할 2가지, \(p_2(4)=1\), 3개로 분할 1가지, \(p_3(4)=1\), 4개로 분할 1가지, \(p_4(4)=1\)로 총 5가지가 있다는 것을 보여줍니다. 이들 모든 경우를 합해서, 분할 함수 \(p(4)=5\)라고 표시합니다.

그러므로, 자연수의 분할은

\(\quad\)\(n=n_1+n_2+n_3+\cdots+n_k\;(n \ge n_1 \ge n_2 \ge n_3 \ge\cdots\ge n_k)\)

와 같이 나타내며,

\(\quad\)\(p(n)\): 전체 경우의 수

\(\quad\)\(p_k(n)\): 자연수 \(n\)을 \(k\)개의 부분으로 분할하는 경우의 수

\(P(n,k)\)는 순열을 나타내는 것이며, 자연수의 분할은 함수 \(p(n)\)으로 나타내고, \(p_k(n)\)는 \(k\) 분할로 제한된 분할을 나타냅니다.

예를 들어,

\(\quad\)\(p(4)=5\),

\(\quad\)\(p_2(4)=2\).

자연수 n의 분할의 수는 다음과 같은 특징을 가집니다:

\(\quad\)\(p(n)=p_1(n)+p_2(n)+p_3(n)+\dots+p_n(n)\)

\(\quad\)\(p_1(n)=1, p_n(n)=1\)

\(p_k (n)\)의 성질

\(S(n,k)\)의 재귀 관계처럼, \(p_k(n)\)에도 비슷한 재귀 관계가 있습니다. 

\(\quad\)(가) 1이 하나의 분할로 존재하는 경우

\(\quad\)(나) 1이 분할로 존재하지 않는 경우

(가)는 \(p_k(n)\)에서 이미 1개의 분할이 존재하므로, 나머지 \(n-1\)에서 \(k-1\)개의 분할을 해야 합니다. (나)는 1의 분할이 없어야 하기 때문에, 분할해야 할 \(k\)개에 미리 1을 분배하고, 나머지 \(n–k\)를 \(k\)개로 분할해서 이미 분할되어 있는 \(k\)개의 1과 더합니다. 즉,

\(\quad\)\(p_k(n)=p_{k-1}(n-1)+p_k(n-k)\)

이 경우에 \(n-k<k\)이면, 자연수보다 분할해야 하는 개수가 더 크기 때문에, \(p_k(n-k)=0\)입니다.
\(p_k(n)\)은 또 다른 성질도 있습니다. 예를 들어, 7을 3개의 자연수로 분할하는 경우에 다음과 같이 나타내는 것을 생각해 보십시오:

\(\quad\)\(7=(1+a)+(1+b)+(1+c)\) (\(a,b,c\) 비-음의 정수).

이때, \(a+b+c=4\)이고, \(a,b,c\)는 0이 가능하므로 4를 1개 또는 2개, 또는 3개의 자연수로 분할하는 경우와 같습니다. 따라서

\(p_3(7)=p_1(4)+p_2(4)+p_3(4)\).

따라서, \(p_k(n)\)는

i) 만약 \(n-k \ge k\)이면, 다음과 같이 쓸 수 있습니다:

\(\quad\)\(p_k(n)=p_1(n-k)+p_2(n-k)+\cdots+p_k(n-k)\)

ii) 만약 \(n-k < k\)이면, 다음과 같이 쓸 수 있습니다:

\(\quad\)\(p_k(n)=p_1(n-k)+p_2(n-k)+\cdots+p_{n-k}(n-k)\)

사실 위의 경우를 2개로 나눌 필요는 없습니다. 왜냐하면, 자연수보다 분할이 더 큰 경우, 즉,

\(\quad\)\(n<k\)이면, \(p_k(n)=0\)

이기 때문입니다.

퍼얼스 다이어그램 또는 영 다이어그램

자연수 4를 분할하는 방법은 다음과 같이 퍼얼스 다이어그램을 그릴 수 있습니다.

퍼얼스 다이어그램은 위와 같이 점(또는 원)을 이용해서 자연수 분할을 그래픽적으로 시각화합니다. 영 다이어그램은 상자(또는 사각형)를 이용해서 시각화합니다. 시각화는 다음 논리로 쉽게 그릴 수 있습니다.

• 행의 마지막의 점을 아래 행으로 내려서 끝에 붙입니다.
• 행 사이의 점의 개수는 위의 것이 아래 것보다 항상 크거나 같습니다.
• 만약 행의 끝점이 위의 조건을 만족하지 못하면 다음 행으로 이동해서 진행합니다.
• 아래 행에서 더 이상 진행할 것이 없으면, 맨 위의 행으로 이동합니다.
• 모두 같아지면 종료합니다.

홀수는 다음과 같이 진행됩니다.

만약 행을 분할의 개수가 정해져 있을 때, 예를 들어, \(P_{3}(10)\)와 같은 것은 퍼얼스 다이어그램을 어떻게 그릴까요? 이때에는 1행에 8개, 2행에 1개, 3행에 1개를 두고 다이어그램을 그리기 시작해서, 4행을 만들기 전에 끝내야 합니다.