자연수의 분할수(integer partitions)

수학노트
http://bomber0.myid.net/ (토론)님의 2009년 11월 27일 (금) 22:28 판
둘러보기로 가기 검색하러 가기
이 항목의 스프링노트 원문주소

 

 

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

 

 

수가 작은 경우의 분할수

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

 

 

 

 

 

  • 분할수가 상당히 빨리 증가함을 볼 수 있음

 

 

근사공식

함수의 크기

함수의 정확한 값보다 그것의 대충의 크기를 알고 싶은 것이므로,'asymptotic'이라는 개념을 도입하자.


두 함수 f(x)와 g(x)가 위와 같은 조건을 만족할 때, 두 함수가 'asymptotic'이라고 하고, f(x)~g(x) 라고 표현한다. 이것의 의미는 x가 충분히 크다면, 두 함수의 행동이 비슷하다는 것을 뜻한다. 물론, 함수의 정확한 값은 차이가 날 수도 있지만, 눈을 크게 뜨고 멀리서 바라보면, 둘이 같다는 것이다. 가령 이라는 함수가 있다고 생각해 보자. x값이 작을 때야, 가 함수값에 꽤나 영향을 미치겠지만, x가 커지면 커질수록, 는 거대한 지수함수 앞에서 미미한 존재가 될 뿐이다. 즉 함수의 행동을 지배하는 것은 지수함수이다. 이러한 sense에서 asymptotic을 이해하자.

정수에 관계된 함수의 큰 행동을 이해하는 것은 수학의 어렵고도 중요한 주제중의 하나이다.

MacMahon의 경험을 복원한다!

지금 이것을 만들게 된 동기는 어느 책에서 다음과 같은 문구를 읽고 나서이다.

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는 적당한 상수) 너무 대충 하는 것이 아닌가 하는 생각이 들겠지만, 무언가를 발견한다는 것은 개연성 있는 직관이면 족한 것이다!
그럼 이제 맥머흔 소령의 경험을 재현하자!

다음 그림은 Partition Number를 1부터 200까지 아래로 죽 늘어뜨린 다음에 글씨체를 상당히 작게 한 것이다. 그 다음에 아래위를 뒤집었다.짜잔!!!


당신의 눈에도 포물선이 보이는가?
숫자같이 보이지 않겠지만


요런 것을 글씨체를 작게 하면 저렇게 된다.
위에서 얻은 그림을 가로로 좀 더 잡아 당겨서 다음 그림을 얻었다.


정말로 꽤나 그럴듯한 포물선이다.
이것으로 미루어 보아 맥머흔의 글씨체는 상당히 옆으로 퍼졌던 것이 아닌가 하는 생각을 해 본다.

맥머흔의 관찰은 옳았던가?

맥머흔의 이 매우 흥미로운 경험은 후대의 연구에 의하여, 틀린 것으로 판명되었다. 알려진 결과에 의하면 분할수의 근사공식은 다음과 같다.

\(p(n) \approx \frac {e^{\pi\sqrt{\frac{2n}{3}}}} {4\sqrt{3}n}\)
엄밀히 말해 맥머흔의 추론은 틀린 것이다. 그러나 맥머흔의 관찰이 의미없는 것은 아니다. 비록 정확하지는 못했지만 n이 상대적으로 작았다는 것을 고려한다면, 맥머흔의 경험은 공식에 그럴듯한 접근은 한 것이다. 또한 partition number에도 어떠한 규칙이 있을 가능성을 보였다는 점에서 충분히 의미가 있는 일일테니까.
이제 위의 근사공식이 얼마나 그럴듯한 것인지를 확인하며 마무리를 하자.

위에서 얻은 근사공식은 \(n=200\)인 경우, 그 값이 \(4.10025 \times 10^{12}\)정도 된다. 한편, 이 경우 분할수의 값은 p(200)=3972999029388이므로, 공식이 정확히 맞지는 않아도, 꽤나 비슷하다는 것을 알 수 있을 것이다.

 

 

생성함수

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

 

 

분할수의 점화식

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

 

 

 

메모

 

 

재미있는 사실

 

 

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

 

 

관련된 다른 주제들

 

 

관련도서 및 추천도서

 

 

관련논문

 

 

사전 형태의 자료

 

관련기사

 

 

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