"자연수의 분할수(integer partitions)"의 두 판 사이의 차이
둘러보기로 가기
검색하러 가기
Pythagoras0 (토론 | 기여) |
Pythagoras0 (토론 | 기여) |
||
| 4번째 줄: | 4번째 줄: | ||
* 주어진 자연수를 자연수 몇 개로 쪼개서 그 합으로 쓸 수 있는 방법의 수 | * 주어진 자연수를 자연수 몇 개로 쪼개서 그 합으로 쓸 수 있는 방법의 수 | ||
* 가령 주어진 수가 3 이라면, 1+1+1, 2+1, 3 세 가지 방법 | * 가령 주어진 수가 3 이라면, 1+1+1, 2+1, 3 세 가지 방법 | ||
| − | * 주어진 자연수가 5 라면 1+1+1+1+1, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, | + | * 주어진 자연수가 5 라면 1+1+1+1+1, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, 5 일곱가지 방법 |
| − | * 자연수 n에 대하여 이런 식으로 표현할 수 있는 방법의 | + | * 자연수 n에 대하여 이런 식으로 표현할 수 있는 방법의 수를 <math>p(n)</math> (n의 분할수, partition number)라 한다. |
| − | ** p(3)=3, p(5)=7 | + | ** $p(3)=3, p(5)=7$ |
* 정수론, 조합론, 통계물리 등에서 중요한 역할 (모듈라 형식과 q-초기하급수 등) | * 정수론, 조합론, 통계물리 등에서 중요한 역할 (모듈라 형식과 q-초기하급수 등) | ||
==수가 작은 경우의 분할수== | ==수가 작은 경우의 분할수== | ||
| − | \begin{array}{ | + | \begin{array}{c|c} |
n & p(n) \\ | n & p(n) \\ | ||
\hline | \hline | ||
| 37번째 줄: | 37번째 줄: | ||
* [[200까지의 분할수 목록]] | * [[200까지의 분할수 목록]] | ||
| − | + | ||
==생성함수== | ==생성함수== | ||
| − | * | + | * 분할수의 [[생성함수]]는 무한곱으로 표현가능 |
| − | :<math>\sum_{n=0}^\infty p(n)q^n= 1+q+2 q^2+3 q^3+5 q^4+7 q^5+11 q^6+15 q^7+22 q^8+30 q^9+42 q^{10}+\cdots</math | + | :<math>\sum_{n=0}^\infty p(n)q^n= 1+q+2 q^2+3 q^3+5 q^4+7 q^5+11 q^6+15 q^7+22 q^8+30 q^9+42 q^{10}+\cdots</math> |
:<math>\sum_{n=0}^\infty p(n)q^n = \prod_{n=1}^\infty \frac {1}{1-q^n} = \prod_{n=1}^\infty (1-q^n)^{-1} </math> | :<math>\sum_{n=0}^\infty p(n)q^n = \prod_{n=1}^\infty \frac {1}{1-q^n} = \prod_{n=1}^\infty (1-q^n)^{-1} </math> | ||
| − | * [[분할수의 생성함수(오일러 함수)]] | + | * [[분할수의 생성함수(오일러 함수)]] 항목을 참조 |
==분할수의 점화식== | ==분할수의 점화식== | ||
| − | * 분할수는 아래의 점화식을 만족시키는데, 컴퓨터가 등장하기 | + | * 분할수는 아래의 점화식을 만족시키는데, 컴퓨터가 등장하기 전에는 이 점화식을 이용하여, 분할수의 표를 작성했을 것이라 추측됨 |
| + | :<math>p(k) =p(k-1) + p(k-2)-p(k-5)-p(k-7)+p(k-12)+p(k-15)-p(k-22)+\cdots</math> | ||
| − | + | ;증명 | |
| − | |||
| − | |||
[[오일러의 오각수정리(pentagonal number theorem)]] 를 이용하자. | [[오일러의 오각수정리(pentagonal number theorem)]] 를 이용하자. | ||
| 61번째 줄: | 60번째 줄: | ||
:<math>\sum_{n=0}^\infty p(n)q^n = \prod_{n=1}^\infty (1-q^n)^{-1} </math> 의 역수이므로, 둘을 곱하여 | :<math>\sum_{n=0}^\infty p(n)q^n = \prod_{n=1}^\infty (1-q^n)^{-1} </math> 의 역수이므로, 둘을 곱하여 | ||
| − | :<math>(\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</math> | + | :<math>(\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</math> |
을 얻는다. 이로부터 | 을 얻는다. 이로부터 | ||
:<math>p(k) =p(k-1) + p(k-2)-p(k-5)-p(k-7)+p(k-12)+p(k-15)-p(k-22)+\cdots</math> | :<math>p(k) =p(k-1) + p(k-2)-p(k-5)-p(k-7)+p(k-12)+p(k-15)-p(k-22)+\cdots</math> | ||
| − | 를 얻을 수 있다. | + | 를 얻을 수 있다. ■ |
| − | + | ===예=== | |
| − | + | * <math>p(10)=42</math> | |
| − | + | * <math>p(9) + p(8)-p(5)-p(3)=30+22-7-3=42</math> | |
| − | + | ||
| − | + | ||
==분할수가 만족시키는 합동식== | ==분할수가 만족시키는 합동식== | ||
| − | * 라마누잔의 발견:<math>p(5k+4)\equiv 0 \pmod 5</math>:<math>p(7k+5)\equiv 0 \pmod 7</math>:<math>p(11k+6)\equiv 0 \pmod {11}</math | + | * 라마누잔의 발견:<math>p(5k+4)\equiv 0 \pmod 5</math>:<math>p(7k+5)\equiv 0 \pmod 7</math>:<math>p(11k+6)\equiv 0 \pmod {11}</math> |
* [[분할수가 만족시키는 합동식]] 항목 참조 | * [[분할수가 만족시키는 합동식]] 항목 참조 | ||
| − | + | ||
| − | + | ||
==분할수의 근사공식== | ==분할수의 근사공식== | ||
| 94번째 줄: | 93번째 줄: | ||
| − | + | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==관련된 항목들== | ==관련된 항목들== | ||
| 118번째 줄: | 105번째 줄: | ||
* [[Q-초기하급수(q-hypergeometric series)와 양자미적분학(q-calculus)|q-초기하급수(q-hypergeometric series)]] | * [[Q-초기하급수(q-hypergeometric series)와 양자미적분학(q-calculus)|q-초기하급수(q-hypergeometric series)]] | ||
| − | |||
| − | + | ===관련된 고교수학 또는 대학수학=== | |
| + | |||
| + | * [[일변수미적분학]] | ||
| + | * [[해석개론]] | ||
| + | * [[복소함수론]] | ||
| + | * [[초등정수론]] | ||
| + | * [[해석적정수론]] | ||
| + | |||
| + | |||
| + | |||
| + | ==매스매티카 파일 및 계산 리소스== | ||
| + | * https://docs.google.com/file/d/0B8XXo8Tve1cxbXN3Zm5LZnFPNU0/edit | ||
| + | |||
==관련도서== | ==관련도서== | ||
| 126번째 줄: | 124번째 줄: | ||
| − | + | ||
| − | + | ||
==리뷰논문, 에세이, 강의노트== | ==리뷰논문, 에세이, 강의노트== | ||
| 134번째 줄: | 132번째 줄: | ||
* George E. Andrews [http://www.ams.org/bull/2007-44-04/S0273-0979-07-01180-9/ Euler's "De Partitio Numerorum"], Bull. Amer. Math. Soc. 44 (2007), 561-573. | * George E. Andrews [http://www.ams.org/bull/2007-44-04/S0273-0979-07-01180-9/ Euler's "De Partitio Numerorum"], Bull. Amer. Math. Soc. 44 (2007), 561-573. | ||
* P. Shiu, [http://www.jstor.org/stable/3618767 Computations of the Partition Function] <cite>The Mathematical Gazette</cite>, Vol. 81, No. 490 (Mar., 1997), pp. 45-52 | * P. Shiu, [http://www.jstor.org/stable/3618767 Computations of the Partition Function] <cite>The Mathematical Gazette</cite>, Vol. 81, No. 490 (Mar., 1997), pp. 45-52 | ||
| − | + | ||
2014년 1월 8일 (수) 15:55 판
개요
- 분할수란 주어진 자연수를 자연수들의 덧셈으로 표현하는 방법의 수를 말함.
- 주어진 자연수를 자연수 몇 개로 쪼개서 그 합으로 쓸 수 있는 방법의 수
- 가령 주어진 수가 3 이라면, 1+1+1, 2+1, 3 세 가지 방법
- 주어진 자연수가 5 라면 1+1+1+1+1, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, 5 일곱가지 방법
- 자연수 n에 대하여 이런 식으로 표현할 수 있는 방법의 수를 \(p(n)\) (n의 분할수, partition number)라 한다.
- $p(3)=3, p(5)=7$
- 정수론, 조합론, 통계물리 등에서 중요한 역할 (모듈라 형식과 q-초기하급수 등)
수가 작은 경우의 분할수
\begin{array}{c|c} n & p(n) \\ \hline 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 \\ \end{array}
생성함수
- 분할수의 생성함수는 무한곱으로 표현가능
\[\sum_{n=0}^\infty p(n)q^n= 1+q+2 q^2+3 q^3+5 q^4+7 q^5+11 q^6+15 q^7+22 q^8+30 q^9+42 q^{10}+\cdots\] \[\sum_{n=0}^\infty p(n)q^n = \prod_{n=1}^\infty \frac {1}{1-q^n} = \prod_{n=1}^\infty (1-q^n)^{-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\]
- 증명
오일러의 오각수정리(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(10)=42\)
- \(p(9) + p(8)-p(5)-p(3)=30+22-7-3=42\)
분할수가 만족시키는 합동식
- 라마누잔의 발견\[p(5k+4)\equiv 0 \pmod 5\]\[p(7k+5)\equiv 0 \pmod 7\]\[p(11k+6)\equiv 0 \pmod {11}\]
- 분할수가 만족시키는 합동식 항목 참조
분할수의 근사공식
\[p(n) \approx \frac {e^{\pi\sqrt{\frac{2n}{3}}}} {4\sqrt{3}n}\]
메모
관련된 항목들
- 라마누잔의 수학
- 데데킨트 에타함수
- Farey series
- 하디-라마누잔 분할수 공식
- 수학사 연표
- 오일러의 오각수정리(pentagonal number theorem)
- q-초기하급수(q-hypergeometric series)
관련된 고교수학 또는 대학수학
매스매티카 파일 및 계산 리소스
관련도서
- George E. Andrews, The Theory of Partitions
리뷰논문, 에세이, 강의노트
- Partitions : at the interface of q-series and modular forms Andrews, George E., 2003
- George E. Andrews Euler's "De Partitio Numerorum", Bull. Amer. Math. Soc. 44 (2007), 561-573.
- P. Shiu, Computations of the Partition Function The Mathematical Gazette, Vol. 81, No. 490 (Mar., 1997), pp. 45-52