자연수의 분할

위키백과, 우리 모두의 백과사전.
(분할수에서 넘어옴)
이동: 둘러보기, 검색
분할 10=5+4+1을 나타내는 영 타블로

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

정의[편집]

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

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

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

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

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

성질[편집]

생성함수[편집]

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

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

점근 공식[편집]

매우 큰 에 대하여, 분할수 은 다음과 같은 점근 공식을 따른다. 이는 고드프리 해럴드 하디스리니바사 라마누잔이 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의 분할수는 이 된다.

참고 문헌[편집]

  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. 

바깥 고리[편집]