"자연수의 분할수(integer partitions)"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
(피타고라스님이 이 페이지의 위치를 <a href="/pages/4792049">q-초기하급수(q-hypergeometric series)와 양자미적분학(q-calculus)</a>페이지로 이동하였습니다.)
86번째 줄: 86번째 줄:
 
 
 
 
  
−
<h5>근사공식</h5>
+
<h5>분할수의 근사공식</h5>
  
−
'''함수의 크기'''
+
<math>p(n) \approx \frac {e^{\pi\sqrt{\frac{2n}{3}}}} {4\sqrt{3}n}</math>
−
 
 
−
함수의 정확한 값보다 그것의 대충의 크기를 알고 싶은 것이므로,'asymptotic'이라는 개념을 도입하자.
 
−
 
 
−
<br> 두 함수 f(x)와 g(x)가 위와 같은 조건을 만족할 때, 두 함수가 'asymptotic'이라고 하고, f(x)~g(x) 라고 표현한다. 이것의 의미는 x가 충분히 크다면, 두 함수의 행동이 비슷하다는 것을 뜻한다. 물론, 함수의 정확한 값은 차이가 날 수도 있지만, 눈을 크게 뜨고 멀리서 바라보면, 둘이 같다는 것이다. 가령 이라는 함수가 있다고 생각해 보자. x값이 작을 때야, 가 함수값에 꽤나 영향을 미치겠지만, x가 커지면 커질수록, 는 거대한 지수함수  앞에서 미미한 존재가 될 뿐이다. 즉 함수의 행동을 지배하는 것은 지수함수이다. 이러한 sense에서 asymptotic을 이해하자.
 
−
 
 
−
정수에 관계된 함수의 큰 행동을 이해하는 것은 수학의 어렵고도 중요한 주제중의 하나이다.
 
−
 
 
−
'''MacMahon의 경험'''
 
−
 
 
−
{| class="g2"
 
−
|-
 
−
| The table can be extended further of course no apparent pattern emerges. There is a famous story concerning the search for some kind of pattern in this table. This is told of Major MacMahon who kept a list of these partition numbers arranged one under another up into the hundreds. It suddenly occurred to him that, viewed from a distance, the outline of the digits seemed to form a parabola! Thus the number of digits in p(n), the number of partitions of n, is around  or, p(n) itself is very roughly  . The first crude assesment of p(n)!
 
−
Donald J.Newman 이 지은 'Analytic Number Theory'중에서
 
−
 
 
−
|-
 
−
| (생략)좀 떨어진 거리에서, 수의 끝부분은 포물선을 이룬다는 사실을 깨닫게 되었다!(생략)
 
−
|}
 
−
 
 
−
위에 써 있는 내용을 이해하는 것은 log 함수의 이해를 필요로 한다. p(n)가 쓰여진 길이는 그 것의 자릿수에 비례하는 것이고, 한편 log p(n) 값은 그 자릿수에 비례한다. p(n)의 자릿수가 대충 이라면 라는 얘기가 된다. (여기서 C는 적당한 상수) 너무 대충 하는 것이 아닌가 하는 생각이 들겠지만, 무언가를 발견한다는 것은 개연성 있는 직관이면 족한 것이다!<br> 그럼 이제 맥머흔 소령의 경험을 재현하자!
 
−
 
 
−
다음 그림은 Partition Number를 1부터 200까지 아래로 죽 늘어뜨린 다음에 글씨체를 상당히 작게 한 것이다. 그 다음에 아래위를 뒤집었다.짜잔!!!
 
−
 
 
−
<br> 당신의 눈에도 포물선이 보이는가?<br> 숫자같이 보이지 않겠지만
 
−
 
 
−
 
 
−
 
 
−
요런 것을 글씨체를 작게 하면 저렇게 된다.<br> 위에서 얻은 그림을 가로로 좀 더 잡아 당겨서 다음 그림을 얻었다.
 
−
 
 
−
<br> 정말로 꽤나 그럴듯한 포물선이다.<br> 이것으로 미루어 보아 맥머흔의 글씨체는 상당히 옆으로 퍼졌던 것이 아닌가 하는 생각을 해 본다.
 
−
 
 
−
'''맥머흔의 관찰은 옳았던가?'''
 
−
 
 
−
맥머흔의 이 매우 흥미로운 경험은 후대의 연구에 의하여, 틀린 것으로 판명되었다. 알려진 결과에 의하면 분할수의 근사공식은 다음과 같다.
 
−
 
 
−
<math>p(n) \approx \frac {e^{\pi\sqrt{\frac{2n}{3}}}} {4\sqrt{3}n}</math><br> 엄밀히 말해 맥머흔의 추론은 틀린 것이다. 그러나 맥머흔의 관찰이 의미없는 것은 아니다. 비록 정확하지는 못했지만 n이 상대적으로 작았다는 것을 고려한다면, 맥머흔의 경험은 공식에 그럴듯한 접근은 한 것이다. 또한 partition number에도 어떠한 규칙이 있을 가능성을 보였다는 점에서 충분히 의미가 있는 일일테니까.<br> 이제 위의 근사공식이 얼마나 그럴듯한 것인지를 확인하며 마무리를 하자.
 
−
 
 
−
위에서 얻은 근사공식은 <math>n=200</math>인 경우, 그 값이 <math>4.10025 \times 10^{12}</math>정도 된다. 한편, 이 경우 분할수의 값은 p(200)=3972999029388이므로, 공식이 정확히 맞지는 않아도, 꽤나 비슷하다는 것을 알 수 있을 것이다.
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
<h5>하디-라마누잔-라데마커 근사공식</h5>
 
  
 
* [[분할수의 근사 공식 (하디-라마누잔-라데마커 공식)|하디-라마누잔 분할수 공식]] 항목 참조
 
* [[분할수의 근사 공식 (하디-라마누잔-라데마커 공식)|하디-라마누잔 분할수 공식]] 항목 참조

2012년 8월 26일 (일) 04:45 판

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

 

 

개요
  • 분할수란 주어진 자연수를 자연수들의 덧셈으로 표현하는 방법의 수를 말함.
  • 주어진 자연수를 자연수 몇 개로 쪼개서 그 합으로 쓸 수 있는 방법의 수
  • 가령 주어진 수가 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

 

 

수가 작은 경우의 분할수

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= 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(10)=42\)
    • \(p(9) + p(8)-p(5)-p(3)=30+22-7-3=42\)

 

 

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

 

 

분할수의 근사공식

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

 

 

 

메모

 

 

재미있는 사실

 

 

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

 

 

관련된 항목들

 

 

관련도서 및 추천도서

 

 

관련논문

 

 

사전 형태의 자료

 

블로그
원본 주소 "https://wiki.mathnt.net/index.php?title=자연수의_분할수(integer_partitions)&oldid=17349"