자연수의 분할수(integer partitions)

간단한 소개

• 분할수란 주어진 자연수를 자연수들의 덧셈으로 표현하는 방법의 수를 말함.

 

Partition Number란? 주어진 자연수를 자연수 몇 개로 쪼개서 그 합으로 쓸 수 있는 방법의 수를 말한다. 가령 주어진 수가 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 가 된다. 앞으로 할 얘기는 바로 이 partition number 에 관한 것이다. 몇몇 Partition number 몇 가지 수에 대한 partition number를 적어 보면, n P(n) 1 1 10 42 20 627 30 5604 40 37338 50 204226 60 966467 70 4087968 80 15796476 90 56634173 100 190569292 110 607163746 120 1844349560 130 5371315400 140 15065878135 150 40853235313 160 107438159466 170 274768617130 180 684957390936 190 1667727404093 200 3972999029388 표를 보면, partition Number가 상당히 빨리 증가한다는 사실을 알 수 있을 것이다. 그러면 이것이 얼마나 빨리 증가하고 있는가? 이것이 우리의 문제이다. 함수의 크기 함수의 정확한 값보다 그것의 대충의 크기를 알고 싶은 것이므로,'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까지 아래로 죽 늘어뜨린 다음에 글씨체를 상당히 작게 한 것이다. 그 다음에 아래위를 뒤집었다.짜잔!!! 당신의 눈에도 포물선이 보이는가? 숫자같이 보이지 않겠지만 요런 것을 글씨체를 작게 하면 저렇게 된다. 위에서 얻은 그림을 가로로 좀 더 잡아 당겨서 다음 그림을 얻었다. 정말로 꽤나 그럴듯한 포물선이다. 이것으로 미루어 보아 맥머흔의 글씨체는 상당히 옆으로 퍼졌던 것이 아닌가 하는 생각을 해 본다.-.- 맥머흔의 관찰은 옳았던가? 맥머흔의 이 매우 흥미로운 경험은 후대의 연구에 의하여, 틀린 것으로 판명되었다. 알려진 결과에 의하면 partition number의 asymptotic formula는 다음과 같다. 무지하게 복잡한 공식이다. 맥머흔의 추론은 틀린 것이다. 틀렸다고 해서 맥머흔의 관찰이 의미없는 것은 아니다. 비록 정확하지는 못했지만 n이 상대적으로 작았다는 것을 고려한다면, 맥머흔의 경험은 공식에 그럴듯한 접근은 한 것이다. 또한 partition number에도 어떠한 규칙이 있을 가능성을 보였다는 점에서 충분히 의미가 있는 일일테니까. 이제 위의 asymptotic formula가 얼마나 그럴듯한 것인지를 확인하며 마무리를 하자. 위에서 얻은 asymptotic formula에 200을 넣으면, 그 값은이라고 한다. 한편, 정확한 값 p(200)=3972999029388이므로, 공식이 정확히 맞지는 않아도, 꽤나 비슷하다는 것을 알 수 있을 것이다. 물론 큰 sense에서 !

 

관련된 학부 과목과 미리 알고 있으면 좋은 것들

• 일변수미적분학
• 해석개론
• 복소함수론
• 초등정수론[[search?q=정수론&parent id=1950882|]]

 

관련된 대학원 과목

• 해석적정수론

 

관련된 다른 주제들

• 라마누잔의 수학

 

표준적인 도서 및 추천도서

• The Theory of Partitions
  
  • George E. Andrews
    

참고할만한 자료

• Computations of the Partition Function
  
  • P. Shiu
  • The Mathematical Gazette, Vol. 81, No. 490 (Mar., 1997), pp. 45-52
• Dyson's crank of a partition
  
  • George E. Andrews and F. G. Garvan
  • Source: Bull. Amer. Math. Soc. (N.S.) Volume 18, Number 2 (1988), 167-171

 

위키링크

• Partition (number theory)