주 메뉴 열기
분할 10=5+4+1을 나타내는 페러스 그림

정수론에서, 자연수 분할(自然數分割, 영어: integer partition)은 어떤 자연수를 양의 정수들의 합으로 나타내는 방법이다.

목차

정의편집

자연수  분할  은 다음을 만족시키는, 양의 정수들의 중복집합이다.

 

분할은 페러스 그림으로 나타낼 수 있다. 이 경우 각 가로의 길이는 분할의 각 원소의 크기에 대응한다. 분할수(分割數, 영어: partition number)   의 분할들의 수이다. 분할수의 값들은 다음과 같다( 부터 시작).

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, … (OEIS의 수열 A000041)

  의 분할들 가운데, 원소가 중복되지 않는 것들의 수이다. 이는 다음과 같다( 부터 시작).

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, … (OEIS의 수열 A000009)

성질편집

생성함수편집

분할수의 생성함수는 다음과 같다.

 
 

여기서  데데킨트 에타 함수이며,  이다.

점근 공식편집

매우 큰  에 대하여, 분할수  은 다음과 같은 점근 공식을 따른다. 이는 고드프리 해럴드 하디스리니바사 라마누잔이 1918년 하디-리틀우드 원 방법으로 유도하였고, 1942년에 에르되시 팔이 기초적인 기법만으로 재증명하였다.[1]

 

마찬가지로,  은 다음과 같은 점근 공식을 따른다.[2]

 

편집

양의 정수 3을 생각해 보자.

  1. 3 = 3
  2. 3 = 2 + 1
  3. 3 = 1 + 1 + 1

으로 총 세 가지의 경우가 있으므로, 3의 분할수는  가 된다.

4일 때는,

  1. 4 = 4
  2. 4 = 3 + 1
  3. 4 = 2 + 2
  4. 4 = 2 + 1 + 1
  5. 4 = 1 + 1 + 1 + 1

총 다섯 가지이므로, 4의 분할수는  이 된다.

공액분할편집

 를 자연수 n의 분할이라 하자. 분할  페러스 그림(영어: Ferrers diagram)에 나타내었을 때,  번째 열의 칸의 개수를  라 하면  을 공액분할(영어: conjugate partition)이라 한다.

예를 들어 그림1 과 같은 14의 분할  의 공액분할은 그림 2의  이 된다.

공액분할의 활용편집

각 부분이   이하인  의 분할의 수는 부분의 수가   이하인  의 분할의 수와 같음이 알려져 있는데, 이는 공액분할로 쉽게 이해할 수 있다.

각 부분이  이하이면 주대각선에 대해 대칭하였을 때, 세로 칸의 개수가  이하가 되므로 부분의 수가  이하임을 알 수 있다.

참고 문헌편집

  1. Erdős, Pál (1942). “On an elementary proof of some asymptotic formulas in the theory of partitions”. 《Annals of Mathematics (series 2)》 (영어) 43: 437–450. Zbl 0061.07905. 
  2. Ayoub, Raymond George (1963). 《An Introduction to the analytic theory of numbers》. Mathematical Surveys (영어) 10. American Mathematical Society. OCLC 476776. Zbl 0128.04303. 
  • George E. Andrews, Kimmo Eriksson (2004). 《Integer Partitions》 (영어). Cambridge University Press. ISBN 0-521-60090-1. 
  • Andrews, George E. (1976). 《The Theory of partitions》. Encyclopedia of Mathematics and its Applications (영어) 2. Cambridge University Press. ISBN 0-521-63766-X. 
  • Apostol, Tom M. (1990) [1976]. 《Modular functions and Dirichlet series in number theory》. Graduate Texts in Mathematics (영어) 41 2판. Springer. ISBN 0-387-97127-0. Zbl 0697.10023. 
  • Macdonald, Ian G. (1979). 《Symmetric functions and Hall polynomials》. Oxford Mathematical Monographs (영어). Oxford University Press. ISBN 0-19-853530-9. Zbl 0487.20007. 
  • Nathanson, M.B. (2000). 《Elementary methods in number theory》. Graduate Texts in Mathematics (영어) 195. Springer-Verlag. ISBN 0-387-98912-9. Zbl 0953.11002. 
  • Bóna, Miklós (2002). 《A walk through combinatorics: An introduction to enumeration and graph theory》 (영어). World Scientific. ISBN 981-02-4900-4. 

외부 링크편집