자연수 분할

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

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

정의

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

$n_1+\cdots +n_k=n$

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

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, … 틀:OEIS

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

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, … 틀:OEIS

성질

생성 함수

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

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

$\sum _{n=0}^{\mathrm{\infty }}q(n)x^n=\prod _{n=1}^{\mathrm{\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\}$의 켤레 분할(-分割, 틀:Llang) $\{m_1,\dots ,m_l\}$은 페러스 그림의 각 세로의 길이로 구성된 새로운 $n$의 분할이다. 즉, 페러스 그림의 가로와 세로를 전치하여 얻는 분할이다. 구체적으로는 다음과 같다.

$l=\max \{n_1,\dots ,n_k\}$

$m_i=|\{j=1,\dots ,k:n_j\ge i\}|$

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

예

양의 정수 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정도
• 뉴턴 항등식

각주

• 틀:서적 인용
• 틀:서적 인용
• 틀:서적 인용
• 틀:서적 인용
• 틀:서적 인용
• 틀:서적 인용

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드