자연수 분할

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
분할 9=5+4+1을 나타내는 영 타블로

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

정의[편집]

자연수 n\in\mathbb N분할 \{n_1,\dots,n_k\}은 다음을 만족시키는 중복집합이다.

n_1+\cdots+n_k=n

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

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

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

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

성질[편집]

생성함수[편집]

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

\sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty(1-x^n)^{-1}=\exp(-\pi i\tau/12)\eta(\tau)
\sum_{n=0}^\infty q(n)x^n=\prod_{n=1}^\infty(1+x^n)=\exp(-\pi i\tau/12)\frac{\eta(2\tau)}{\eta(\tau)}

여기서 \eta(\tau)데데킨트 에타 함수이며, x=\exp(2\pi i\tau)이다.

점근 공식[편집]

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

p(n) \sim \frac {1} {4n\sqrt3} \exp\left(\pi \sqrt {\frac{2n}3}\right)

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

q(n)\sim\frac1{4\sqrt[4]{3n^3}}\exp\left(\pi\sqrt{n/3}\right)

[편집]

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

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

으로 총 세가지의 경우가 있으므로, 3의 분할수는 p(3) = 3, q(3)=2가 된다.

4일 때는,

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

총 다섯가지이므로, 4의 분할수는 p(4) = 5, q(4)=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. 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. [1976] (1990). 《Modular functions and Dirichlet series in number theory》, Graduate Texts in Mathematics 41, 2판, Springer. Zbl 0697.10023. ISBN 0-387-97127-0
  • (영어) Macdonald, Ian G. (1979). 《Symmetric functions and Hall polynomials》, Oxford Mathematical Monographs. Oxford University Press. Zbl 0487.20007. ISBN 0-19-853530-9
  • (영어) Nathanson, M.B. (2000). 《Elementary methods in number theory》, Graduate Texts in Mathematics 195. Springer-Verlag. Zbl 0953.11002. ISBN 0-387-98912-9
  • (영어) Bóna, Miklós (2002). 《A walk through combinatorics: An introduction to enumeration and graph theory》. World Scientific. ISBN 981-02-4900-4

바깥 고리[편집]