자연수 분할 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Young diagram for 541 partition.svg|섬네일|분할 10=5+4+1을 나타내는 [[페러스 그림]]]]
[[수론]]에서 '''자연수 분할'''(自然數分割, {{llang|en|integer partition}})은 어떤 [[자연수]]를 양의 정수들의 합으로 나타내는 방법이다.

== 정의 ==
[[자연수]] <math>n\in\mathbb N</math>의 '''분할''' <math>\{n_1,\dots,n_k\}</math>은 다음을 만족시키는, 양의 정수들의 [[중복집합]]이다.
:<math>n_1+\cdots+n_k=n</math>
분할은 [[페러스 그림]]으로 나타낼 수 있다. 이 경우 각 가로의 길이는 분할의 각 원소의 크기에 대응한다.
'''분할수'''(分割數, {{llang|en|partition number}}) <math>p(n)</math>는 <math>n</math>의 분할들의 수이다. 분할수의 값들은 다음과 같다 (<math>n=0,1,2,\dots</math>).
: 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, … {{OEIS|A000041}}
<math>q(n)</math>은 <math>n</math>의 분할들 가운데, 원소가 중복되지 않는 것들의 수이다. 이는 다음과 같다 (<math>n=0,1,2,\dots</math>).
:1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, … {{OEIS|A000009}}

== 성질 ==
=== 생성 함수 ===
분할수의 [[생성함수 (수학)|생성함수]]는 다음과 같다.
:<math>\sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty(1-x^n)^{-1}=\frac{\exp(\pi i\tau/12)}{\eta(\tau)}
</math>
:<math>\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)}
</math>
여기서 <math>\eta(\tau)</math>는 [[데데킨트 에타 함수]]이며, <math>x=\exp(2\pi i\tau)</math>이다.

=== 점근 공식 ===
매우 큰 <math>n</math>에 대하여, 분할수 <math>p(n)</math>은 다음과 같은 점근 공식을 따른다. 이는 [[고드프리 해럴드 하디]]와 [[스리니바사 라마누잔]]이 1918년 [[하디-리틀우드 원 방법]]으로 유도하였고, 1942년에 [[에르되시 팔]]이 기초적인 기법만으로 재증명하였다.<ref>{{저널 인용| zbl=0061.07905 | last=Erdős | first=Pál | authorlink=에르되시 팔 | title=On an elementary proof of some asymptotic formulas in the theory of partitions | journal=Annals of Mathematics (series 2) | volume=43 | pages=437–450 | 날짜=1942|언어=en }}</ref>
:<math>p(n) \sim \frac {1} {4n\sqrt3} \exp\left(\pi \sqrt {\frac{2n}3}\right)</math>
마찬가지로, <math>q(n)</math>은 다음과 같은 점근 공식을 따른다.<ref>{{서적 인용|성=Ayoub|이름=Raymond George|제목=An Introduction to the analytic theory of numbers|출판사=American Mathematical Society|날짜=1963|총서=Mathematical Surveys|권=10|oclc=476776|zbl=0128.04303|언어=en}}</ref>
:<math>q(n)\sim\frac1{4\sqrt[4]{3n^3}}\exp\left(\pi\sqrt{n/3}\right)</math>

=== 켤레 분할 ===
자연수 <math>n</math>의 분할 <math>\{n_1,\dots,n_k\}</math>의 '''켤레 분할'''(-分割, {{llang|en|conjugate partition}}) <math>\{m_1,\dots,m_l\}</math>은 [[페러스 그림]]의 각 세로의 길이로 구성된 새로운 <math>n</math>의 분할이다. 즉, 페러스 그림의 가로와 세로를 전치하여 얻는 분할이다. 구체적으로는 다음과 같다.
:<math>l=\max\{n_1,\dots,n_k\}</math>
:<math>m_i=|\{j=1,\dots,k\colon n_j\ge i\}|</math>
각 원소가 <math>m</math> 이하인 <math>n</math>의 분할과 원소의 개수가 <math>m</math> 이하인 <math>n</math>의 분할은 켤레 분할을 통해 일대일 대응한다. 따라서 각 원소가 <math>m</math> 이하인 <math>n</math>의 분할의 수는 원소의 개수가 <math>m</math> 이하인 <math>n</math>의 분할의 수와 같다. 마찬가지로 가장 큰 원소가 <math>m</math>인 <math>n</math>의 분할의 수는 원소의 개수가 정확히 <math>m</math>인 분할의 수와 같다.<ref name="Sane">{{서적 인용
|성1=Sane
|이름1=Sharad S.
|제목=Combinatorial Techniques
|언어=en
|총서=Texts and Readings in Mathematics
|권=65
|출판사=Hindustan Book Agency
|위치=Gurgaon
|날짜=2013
|isbn=978-93-80250-48-9
|issn=2366-8717
|doi=10.1007/978-93-86279-55-2
}}</ref>{{rp|331, Theorem 13.1.10}}

== 예 ==
양의 정수 3을 생각해 보자.
: 3=3
: 3=2+1
: 3=1+1+1
으로 총 세 가지의 경우가 있으므로,
3의 분할수는 <math>p(3)=3</math>, <math>q(3)=2</math>가 된다.

4일 때는,
: 4=4
: 4=3+1
: 4=2+2
: 4=2+1+1
: 4=1+1+1+1
총 다섯 가지이므로, 4의 분할수는 <math>p(4) = 5</math>, <math>q(4)=2</math>이 된다.

<gallery mode="packed">
파일:페러스 그림.png|분할 10=4+3+1+1+1의 페러스 그림
파일:공액분할.png|분할 10=5+2+2+1의 페러스 그림
</gallery>
10의 분할 <math>\{4,3,1,1,1\}</math>의 켤레 분할은 <math>\{5,2,2,1\}</math>이 된다.

== 같이 보기 ==
* [[인수분해]]
* [[소인수분해]]
* [[집합의 분할]]
* [[12정도]]
* [[뉴턴 항등식]]
== 각주 ==
{{각주}}
* {{서적 인용|author=George E. Andrews, Kimmo Eriksson |title=Integer Partitions |url=https://archive.org/details/integerpartition0000andr |publisher=Cambridge University Press |year=2004 |isbn=0-521-60090-1|언어=en}}
* {{서적 인용|이름=George E.|성=Andrews|제목=The Theory of partitions|날짜=1976|출판사=Cambridge University Press|isbn=0-521-63766-X|총서=Encyclopedia of Mathematics and its Applications|권=2|언어=en}}
* {{서적 인용| last=Apostol | first=Tom M. | title=Modular functions and Dirichlet series in number theory | edition=2판 | series=Graduate Texts in Mathematics | volume=41 | publisher=Springer | year=1990 | origyear=1976 | isbn=0-387-97127-0 | zbl=0697.10023 |언어=en}}
* {{서적 인용| first=Ian G. | last=Macdonald | title=Symmetric functions and Hall polynomials | series=Oxford Mathematical Monographs | publisher=Oxford University Press | year=1979 | isbn=0-19-853530-9 | zbl=0487.20007|언어=en }}
* {{서적 인용| title=Elementary methods in number theory | volume=195 | series=Graduate Texts in Mathematics | first=M.B. | last=Nathanson | publisher=Springer-Verlag | year=2000 | isbn=0-387-98912-9 | zbl=0953.11002 |언어=en}}
* {{서적 인용|이름=Miklós|성=Bóna |title=A walk through combinatorics: An introduction to enumeration and graph theory |url=https://archive.org/details/walkthroughcombi0000bona_j6a7|publisher=World Scientific |year=2002 |isbn=981-02-4900-4|언어=en}}

== 외부 링크 ==
* {{eom|title=Partition}}
* {{매스월드|id=Partition|title=Partition}}
* {{매스월드|id=PartitionFunctionP|title=Partition Function ''P''}}
* {{매스월드|id=PartitionFunctionQ|title=Partition Function ''Q''}}
* {{매스월드|id=PartitionFunctionb|title=Partition Function ''b<sub>k</sub>''}}

[[분류:수론]]
[[분류:조합론]]
[[분류:수론적 함수]]
[[분류:정수열]]