35 1273

Join this notebook

자연수의 분할수(integer partitions)

Edit

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

분할수

개요

분할수란 주어진 자연수를 자연수들의 덧셈으로 표현하는 방법의 수를 말함.
주어진 자연수를 자연수 몇 개로 쪼개서 그 합으로 쓸 수 있는 방법의 수
가령 주어진 수가 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에 대하여 이런 식으로 표현할 수 있는 방법의 수를 (n의 분할수, partition number)라 한다.
- p(3)=3, p(5)=7

수가 작은 경우의 분할수

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

200까지의 분할수 목록
분할수가 상당히 빨리 증가함을 볼 수 있음

생성함수

분할수의 생성함수는 무한곱으로 표현가능

$\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} \right = \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(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}$

하디-라마누잔 분할수 공식 항목 참조

메모

http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf

재미있는 사실

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

관련된 항목들

관련도서 및 추천도서

The Theory of Partitions
- George E. Andrews
도서내검색
- http://books.google.com/books?q=
- http://book.daum.net/search/contentSearch.do?query=
도서검색
- http://www.amazon.com/s/ref=nb_ss_gw?url=search-alias%3Dstripbooks&field-keywords=
- http://book.daum.net/search/mainSearch.do?query=

관련논문

Computations of the Partition Function
- P. Shiu, The Mathematical Gazette, Vol. 81, No. 490 (Mar., 1997), pp. 45-52
Euler's "De Partitio Numerorum"
- George E. Andrews, Bull. Amer. Math. Soc. 44 (2007), 561-573.

사전 형태의 자료

http://ko.wikipedia.org/wiki/
http://en.wikipedia.org/wiki/Partition_(number_theory)
http://en.wikipedia.org/wiki/

블로그

구글 블로그 검색 http://blogsearch.google.com/blogsearch?q=
트렌비 블로그 검색 http://www.trenb.com/search.qst?q=

Tags

오일러,분할,정수론

History

Last edited on 01/29/2011 08:37 by 피타고라스

Comments (0)

Previous Next