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

수학노트
둘러보기로 가기 검색하러 가기
7번째 줄: 7번째 줄:
 
*  자연수 n에 대하여 이런 식으로 표현할 수 있는 방법의 수를 <math>p(n)</math> (n의 분할수, partition number)라 한다.<br>
 
*  자연수 n에 대하여 이런 식으로 표현할 수 있는 방법의 수를 <math>p(n)</math> (n의 분할수, partition number)라 한다.<br>
 
** p(3)=3, p(5)=7
 
** p(3)=3, p(5)=7
−
 
+
* 정수론, 조합론, 통계물리 등에서 중요한 역할 (모듈라 형식과 q-초기하급수 등)
  
  

2013년 3월 17일 (일) 16:09 판

개요

  • 분할수란 주어진 자연수를 자연수들의 덧셈으로 표현하는 방법의 수를 말함.
  • 주어진 자연수를 자연수 몇 개로 쪼개서 그 합으로 쓸 수 있는 방법의 수
  • 가령 주어진 수가 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}{cc} 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(n) \approx \frac {e^{\pi\sqrt{\frac{2n}{3}}}} {4\sqrt{3}n}\]


메모


 

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

 

 

관련된 항목들

 

 

관련도서


 

 

리뷰논문, 에세이, 강의노트

 


사전 형태의 자료

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