자연수 분할

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

분할 10=5+4+1을 나타내는 페러스 그림

정의

자연수 $n\in \mathbb {N}$의 분할 $\{n_{1},\dots ,n_{k}\}$은 다음을 만족시키는, 양의 정수들의 중복집합이다.

$n_{1}+\cdots +n_{k}=n$

분할은 페러스 그림으로 나타낼 수 있다. 이 경우 각 가로의 길이는 분할의 각 원소의 크기에 대응한다. 분할수(分割數, 영어: partition number) $p(n)$는 $n$의 분할들의 수이다. 분할수의 값들은 다음과 같다 ($n=0,1,2,\dots$).

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

$q(n)$은 $n$의 분할들 가운데, 원소가 중복되지 않는 것들의 수이다. 이는 다음과 같다 ($n=0,1,2,\dots$).

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

성질

생성 함수

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

$\sum _{n=0}^{\infty }p(n)x^{n}=\prod _{n=1}^{\infty }(1-x^{n})^{-1}={\frac {\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년에 에르되시 팔이 기초적인 기법만으로 재증명하였다.

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

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

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

켤레 분할

자연수 $n$의 분할 $\{n_{1},\dots ,n_{k}\}$의 켤레 분할(-分割, 영어: conjugate partition) $\{m_{1},\dots ,m_{l}\}$은 페러스 그림의 각 세로의 길이로 구성된 새로운 $n$의 분할이다. 즉, 페러스 그림의 가로와 세로를 전치하여 얻는 분할이다. 구체적으로는 다음과 같다.

$l=\max\{n_{1},\dots ,n_{k}\}$

$m_{i}=|\{j=1,\dots ,k\colon n_{j}\geq i\}|$

각 원소가 $m$ 이하인 $n$의 분할과 원소의 개수가 $m$ 이하인 $n$의 분할은 켤레 분할을 통해 일대일 대응한다. 따라서 각 원소가 $m$ 이하인 $n$의 분할의 수는 원소의 개수가 $m$ 이하인 $n$의 분할의 수와 같다. 마찬가지로 가장 큰 원소가 $m$인 $n$의 분할의 수는 원소의 개수가 정확히 $m$인 분할의 수와 같다.^{:331, Theorem 13.1.10}

예

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

3=3

3=2+1

3=1+1+1

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

4일 때는,

4=4

4=3+1

4=2+2

4=2+1+1

4=1+1+1+1

총 다섯 가지이므로, 4의 분할수는 $p(4)=5$, $q(4)=2$이 된다.

• 
  분할 10=4+3+1+1+1의 페러스 그림
• 
  분할 10=5+2+2+1의 페러스 그림

10의 분할 $\{4,3,1,1,1\}$의 켤레 분할은 $\{5,2,2,1\}$이 된다.

같이 보기

• 인수분해
• 소인수분해
• 집합의 분할
• 12정도
• 뉴턴 항등식

각주

• 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.  CS1 관리 - 추가 문구 (링크)
• 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. 

외부 링크

• “Partition”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Partition”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Partition Function P”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Partition Function Q”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Partition Function b_k”. 《Wolfram MathWorld》 (영어). Wolfram Research.