오일러의 정수 분할

Euler Integer Partition

Theorem(Euler). 임의의 자연수 n을 서로 다른 양의 정수로 나누는 방법의 수는 홀수로 나누는 방법의 수와 같다.

---

$$5=1+4=2+3=5 \\ 5=1+1+1+1+1=3+1+1=5$$

위는 5를 정수 분할한 것로 각각 똑같이 3개이다.

proof. q-series를 정리해서 간단하게 나타낼 수 있다.

$p_d(n)$을 n을 서로 다른 양의 정수로 나누는 방법의 수라고 정의하면 임의의 절댓값이 1보다 작은 q에 대해 계수비교를 하면 다음이 성립한다.

$$\sum _{n=0} ^{\infty} p_d(n) q^n = (1+q)(1+q^2 )(1+q^3 ) \cdots (1+q^k ) \cdots = (-q ; q)_{\infty}$$

마찬가지의 원리로 $p_o (n)$을 n을 홀수로 나누는 방법의 수라고 정의한다면 다음과 같다.

$$\sum _{n=0} ^{\infty} p_o (n) q^n = (1+q+q^2 + \cdots )(1+q^2 + q^4 + \cdots ) \cdots (1+q^j + q^2j + \cdots ) \cdots = \frac {1}{(q;q^2 )}_{\infty}$$

$$\sum _{n=0} ^{\infty} p_d(n) = (-q;q)_{\infty} = \frac {(q^2 ; q^2 )_{\infty}}{(q;q)_{\infty}} = \frac{1}{(q;q^2)_\infty } = \sum _{n=0} ^{\infty} p_o (n) q^n$$

Theorem(확장). 임의의 자연수 n을 k-1개까지 중복을 허락하여 양의 정수로 나누는 방법의 수는 k로 나누어 떨어지지 않는 자연수로 나누는 방법의 수와 같다. (k=2일 때 Euler's theorem)

---

proof. Euler's Theorem과 같은 방식으로 접근이 가능하다.

$p_{k-1} (n)$을 theorem의 전자, $p_{\not\equiv_k 0} (n)$을 theorem의 후자로 놓자.

$$\sum _{n=0} ^\infty p_{k-1} (n) q^n = (1+q + q^2 + \cdots + q^{k-1})(1+q^2 + q^4 + \cdots + q^{2(k-1)})\cdots \\ = \frac {1-q^k}{1-q} \frac {1-q^2k}{1-q^2} \cdots = \frac {(q^k;q^k )_\infty }{(q;q)_\infty } = \sum _{n=0} ^{\infty} p_{\not\equiv _k 0}(n) q^n$$