자연수 분할

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

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

정의

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

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

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

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

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

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

성질

생성 함수

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

${\displaystyle \sum _{n=0}^{\infty }p(n)x^{n}=\prod _{n=1}^{\infty }(1-x^{n})^{-1}={\frac {\exp(\pi i\tau /12)}{\eta (\tau )}}}$

${\displaystyle \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 )}}}$

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

점근 공식

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

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

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

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

켤레 분할

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

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

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

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

예

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

3=3

3=2+1

3=1+1+1

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

4일 때는,

4=4

4=3+1

4=2+2

4=2+1+1

4=1+1+1+1

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

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

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

같이 보기

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