자연수의 분할수(integer partitions)

이 항목의 스프링노트 원문주소

 

 

개요

 

 

수가 작은 경우의 분할수

n  p(n)

0    1
1    1
2    2
3    3
4    5
5    7
6    11
7    15
8    22
9    30
10    42
11    56
12    77
13    101
14    135
15    176
16    231
17    297
18    385
19    490
20    627

 

 

생성함수

\sum_{n=0}^\infty p(n)q^n = \prod_{n=1}^\infty \frac {1}{1-q^n} \right = \prod_{n=1}^\infty (1-q^n)^{-1}

 

 

분할수의 점화식

 

(증명)

오일러의 오각수정리(pentagonal number theorem) 를 이용하자.

(1-q)(1-q^2)(1-q^3) \cdots = 1 - q - q^2 + q^5 + q^7 - q^{12} - q^{15} + q^{22} + q^{26} + \cdots

이는 분할수의 생성함수(오일러 함수)

\sum_{n=0}^\infty p(n)q^n = \prod_{n=1}^\infty (1-q^n)^{-1} 의 역수이므로, 둘을 곱하여

(\sum_{n=0}^\infty p(n)q^n)(1 - q - q^2 + q^5 + q^7 - q^{12} - q^{15} + q^{22} + q^{26} + \cdots)=1 

을 얻는다. 이로부터

p(k) =p(k-1) + p(k-2)-p(k-5)-p(k-7)+p(k-12)+p(k-15)-p(k-22)+\cdots

를 얻을 수 있다.  ■

 

 

분할수가 만족시키는 합동식

 

 

분할수의 근사공식

p(n) \approx \frac {e^{\pi\sqrt{\frac{2n}{3}}}} {4\sqrt{3}n}

 

 

 

메모

 

 

재미있는 사실

 

 

관련된 고교수학 또는 대학수학

 

 

관련된 항목들

 

 

관련도서 및 추천도서

 

 

관련논문

 

 

사전 형태의 자료

 

블로그