맨위로가기

자연수 분할

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

자연수 분할은 주어진 자연수를 양의 정수의 중복 집합으로 나타내는 방법으로, 분할의 개수를 분할수라고 한다. 분할은 페러스 그림이나 영 다이어그램 등으로 시각화할 수 있으며, 분할수 p(n)는 n의 분할 개수를 나타낸다. 분할 함수 p(n)은 생성 함수, 점근 공식, 라마누잔 합동식 등과 관련되어 연구되며, 켤레 분할, 자기 켤레 분할 등의 개념을 통해 분할의 다양한 성질을 탐구한다. 또한, 가우스 이항 계수, 오일러의 분할 항등식, 영 다이어그램, 영 격자 등과 연관되어 조합론, 정수론, 표현론 등 다양한 분야에서 연구된다.

더 읽어볼만한 페이지

  • 수론적 함수 - 디리클레 합성곱
    디리클레 합성곱은 두 수론적 함수를 이용하여 새로운 수론적 함수를 생성하는 연산으로, n의 모든 양의 약수에 대한 함수값의 곱의 합으로 정의되며, 교환, 결합, 분배 법칙을 만족하고 곱셈적 함수의 곱셈성을 보존하며, 디리클레 급수 연구에 활용된다.
  • 수론적 함수 - 체비쇼프 함수
    체비쇼프 함수는 소수 분포 연구에 쓰이는 두 종류의 함수로, 제1종 체비쇼프 함수 \vartheta(x)는 x 이하 소수 p에 대한 \log p의 합, 제2종 체비쇼프 함수 \psi(x)는 x 이하 소수 거듭제곱수 p^k에 대한 \log p의 합으로 정의되며, 소수 정리와 리만 제타 함수를 통한 소수 분포 분석에 활용된다.
  • 조합론 - 집합의 분할
    집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것이며, 동치 관계와 밀접하게 관련되어 있고, 벨 수로 표현되며, 플레잉 카드를 나누는 것과 같은 예시가 있다.
  • 조합론 - 계승 (수학)
    계승은 음이 아닌 정수 n에 대해 1부터 n까지의 자연수를 곱한 값으로, 0의 계승은 1로 정의되며, 대칭군의 크기와 같다는 성질을 통해 기수로 확장될 수 있고, 다중 계승, 지수 계승 등으로 확장 및 응용되어 다양한 분야에서 활용된다.
  • 정수열 - 실베스터 수열
    실베스터 수열은 각 항이 이전 항들의 곱에 1을 더한 값으로 정의되는 정수 수열로서, 재귀적으로 정의되며 이중 지수 함수적으로 증가하고, 이집트 분수 및 탐욕 알고리즘과 관련이 있으며, 역수 합은 1로 수렴한다.
  • 정수열 - 소수 (수론)
    소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이며, 무한히 많고 정수론의 기본 정리에서 중요한 역할을 하며 다양한 분야에 응용된다.
자연수 분할
개요
정의자연수를 양의 정수들의 합으로 표현하는 방법
표기λ ⊢ n (λ는 n의 분할)
분할의 수p(n) (n의 분할의 수)
예시p(4) = 5 (4의 분할은 5가지)
분할의 표현
예시 (4의 분할)4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
관련 개념
페르마 다각형수 정리페르마 다각형수 정리
분할 함수분할 함수

2. 정의

자연수 n의 '''분할'''은 n을 양의 정수들의 합으로 나타내는 방법으로, 순서는 고려하지 않으며 중복을 허용한다. 예를 들어, 5의 분할은 다음과 같이 7가지가 있다.[1]


  • 5
  • 4 + 1
  • 3 + 2
  • 3 + 1 + 1
  • 2 + 2 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1


n의 분할들의 수를 '''분할수'''라고 하며, p(n)으로 표기한다. p(n)의 값은 n=0,1,2,\dots에 대해 다음과 같다.[1]

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

q(n)은 n의 분할 중 중복되는 원소가 없는 분할의 수를 나타낸다. q(n)의 값은 n=0,1,2,\dots에 대해 다음과 같다.[1]

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

분할은 페러스 그림 또는 영 다이어그램을 통해 시각적으로 표현할 수 있다.[1]

2. 1. 표현 방법

자연수 분할은 덧셈 기호를 사용한 표현 외에도, 합의 감소하는 수열, 튜플, 지수를 이용한 표기법 등 다양한 방식으로 표현된다. 예를 들어, 분할 2 + 2 + 1은 튜플 (2, 2, 1)로 쓰거나, 지수가 부분의 반복 횟수를 나타내는 (22, 1)과 같이 더 간결한 형태로 쓸 수 있다.[1]

5의 분할은 1^{m_1}2^{m_2}3^{m_3}\cdots과 같이 표현할 수 있다. 여기서 m_1은 1의 개수, m_2는 2의 개수를 나타내는 식이며, m_i=0인 경우 해당 항은 생략한다. 예를 들어 5의 분할은 이 표기법으로 5^1, 1^1 4^1, 2^1 3^1, 1^2 3^1, 1^1 2^2, 1^3 2^1, 1^5와 같이 나타낼 수 있다.[1]

수 14의 분할 6 + 4 + 3 + 1은 아래 그림과 같이 나타낼 수 있다.




위 그림은 14개의 원을 4개의 행으로 정렬하여 각 행이 분할의 한 부분을 나타내도록 표현한 것이다.[1]

수 4의 5가지 분할은 아래 그림과 같이 나타낼 수 있다.







43 + 12 + 22 + 1 + 11 + 1 + 1 + 1



영 다이어그램은 점 대신 상자 또는 사각형을 사용하여 분할을 나타낸다. 예를 들어, 분할 5 + 4 + 1에 대한 영 다이어그램은 다음과 같다.[1]

같은 분할에 대한 페러스 다이어그램은 아래와 같다.





영 다이어그램은 대칭 함수 및 군 표현론 연구에서 매우 유용하게 활용된다. 영 다이어그램의 상자에 숫자(또는 다른 복잡한 객체)를 채우고 특정 규칙을 적용하면 영 도표라는 객체가 생성되는데, 이는 조합론 및 표현론적 의미를 갖는다. 영 다이어그램은 인접한 사각형들이 연결된 형태, 즉 일종의 폴리오미노이다.[1]

자연수 n에 대해, 수열 \{\lambda_i\}가 다음 조건을 만족하면 'n을 분할한다'고 한다.


  • 각 항은 자연수이며, 유한 개를 제외하고 0이다.
  • 비감소 수열이다. (순서는 중요하지 않다.)
  • 항들의 총합이 n이다.


일반적으로 0인 항은 생략하며, 같은 값을 갖는 항이 여러 개 있을 경우 지수 표기를 사용하여 묶어서 표현한다. (예: k라는 값을 갖는 항이 l개 있다면 k^l로 표기)[1]

3. 분할 함수

분할 함수 p(n)은 주어진 자연수 n의 분할의 개수를 나타내며, q(n)은 n의 분할 중 중복되는 원소가 없는 분할의 개수를 나타낸다. 예를 들어 p(4)=5인데, 이는 정수 4가 1+1+1+1, 1+1+2, 1+3, 2+2, 4와 같이 다섯 가지로 분할될 수 있기 때문이다.

p(n)과 q(n)의 값은 다음과 같다 (n=0,1,2,\dots).

함수값
p(n)1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, …
q(n)1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, …



분할 함수에 대한 폐쇄 형식 표현은 알려져 있지 않지만, 한스 라데마허는 1937년에 수렴 급수로 나타내는 방법을 찾았다. 스리니바사 라마누잔은 분할 함수가 모듈러 산술에서 라마누잔 합동으로 알려진 비자명한 패턴을 갖는다는 것을 발견했다.

3. 1. 생성 함수

:\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)이다.

분할 함수 p(n)의 생성 함수는 다음과 같다.

:\sum_{n=0}^{\infty}p(n)q^n=\prod_{j=1}^{\infty}\sum_{i=0}^{\infty}q^{ji}=\prod_{j=1}^{\infty}(1-q^j)^{-1}.

3. 2. 점근 공식

고드프리 해럴드 하디와 스리니바사 라마누잔이 1918년 하디-리틀우드 원 방법으로 유도하였고, 1942년에 에르되시 팔이 기초적인 기법만으로 재증명한[15] 점근 공식은 다음과 같다.

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

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

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

3. 3. 라마누잔 합동식

분할 함수는 모듈러 산술에서 비자명한 패턴을 갖는데, 이는 스리니바사 라마누잔이 발견하였으며 현재는 라마누잔 합동으로 알려져 있다. 예를 들어, n의 십진수 표현이 숫자 4 또는 9로 끝날 때마다 n의 분할 수는 5로 나누어 떨어진다.[3]

4. 켤레 분할



이 그림을 주 대각선을 따라 뒤집으면 아래 그림과 같이 14의 또 다른 분할 4 + 3 + 3 + 2 + 1 + 1을 얻는다. 이처럼 행과 열을 바꾸어 얻은 분할을 원래 분할의 켤레 분할이라고 한다.

*


↔

6 + 4 + 3 + 1=4 + 3 + 3 + 2 + 1 + 1



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

4. 1. 자기 켤레 분할




다음은 서로 다른 홀수 부분으로 된 분할과 자기 켤레 분할 사이의 전단사(일대일 대응)를 보여주는 예시이다.

↔

x


9 + 7 + 3=5 + 5 + 4 + 3 + 2
서로 다른 홀수자기 켤레


5. 제한된 분할

조합론과 정수론에서, 분할에 제약 조건을 추가하는 경우가 많다.[2] 예를 들어, 정수 8의 분할은 22개인데, 그 중 홀수만을 성분으로 하는 분할과 성분이 모두 다른 분할은 각각 다음과 같이 6개이다.



레온하르트 오일러는 1748년에 임의의 자연수에 대해 홀수만을 성분으로 하는 분할의 수와 성분이 모두 다른 분할의 수가 같다는 것을 증명했다[14](오일러의 분할 항등식).

페레즈 도형과 같은 시각적인 도구를 사용하면 제한된 분할에 대한 결과를 얻는 데 도움이 될 수 있다.

5. 1. 오일러의 분할 항등식

8의 분할 22개 중, 홀수 부분만을 포함하는 분할은 다음과 같이 6가지이다.[3]

어떤 숫자도 두 번 이상 나타나지 않는 분할을 ''서로 다른 부분을 가진 분할''이라고 한다. 8의 서로 다른 부분을 가진 분할 역시 다음과 같이 6가지이다.[3]

이는 일반적인 속성으로, 각 양의 정수에 대해 홀수 부분으로 이루어진 분할의 수는 서로 다른 부분으로 이루어진 분할의 수와 같다. 이 수는 ''q''(''n'')으로 표시된다.[3] 이 결과는 1748년에 레온하르트 오일러에 의해 증명되었으며,[4] 나중에 글레이셔의 정리로 일반화되었다.

''q''(''n'') (서로 다른 부분으로의 분할)의 처음 몇 값은 다음과 같다.

: 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ...

''q''(''n'')의 생성 함수는 다음과 같다.[5]

:\sum_{n=0}^\infty q(n)x^n = \prod_{k=1}^\infty (1+x^k) = \prod_{k=1}^\infty \frac {1}{1-x^{2k-1}} .

오각수 정리는 ''q''에 대한 재귀 관계를 제공한다.[6]

: ''q''(''k'') = ''a''''k'' + ''q''(''k'' - 1) + ''q''(''k'' - 2) - ''q''(''k'' - 5) - ''q''(''k'' - 7) + ''q''(''k'' - 12) + ''q''(''k'' - 15) - ''q''(''k'' - 22) - ...

여기서 ''a''''k''는 어떤 정수 ''m''에 대해 ''k'' = 3''m''2 - ''m''이면 (-1)''m''이고, 그렇지 않으면 0이다.

5. 2. 분할 수의 삼각수

켤레를 취함으로써, 정확히 ''k''개의 부분으로 ''n''을 분할하는 분할 수 는 가장 큰 부분의 크기가 ''k''인 ''n''의 분할 수와 같다.[7] 함수 는 다음 점화식을 만족한다.

:

초깃값은 이며, 이다. 단, 이고 과 가 모두 0이 아닌 경우이다.[7]

함수 ''p''(''n'')은 다음과 같이 구할 수 있다.

:

''k''를 고정하고 ''n''을 변수로 하는 이러한 분할의 생성 함수는 다음과 같다.

:

5. 3. 가우스 이항 계수

부분의 수와 크기를 동시에 제한할 수 있다. ''p(N, M; n)''을 최대 ''M''개의 부분으로, 각 부분의 크기가 최대 ''N''인 ''n''의 분할 수라고 하자. 이는 영 다이어그램이 ''M'' × ''N'' 직사각형 안에 들어맞는 분할과 같다. 다음과 같은 재귀 관계가 성립한다.

:p(N,M;n) = p(N,M-1;n) + p(N-1,M;n-M)

:p(N,M;n) - p(N,M-1;n)은 정확히 ''M''개의 부분으로, 크기가 최대 ''N''인 ''n''의 분할을 나타내며, 각 부분에서 1을 빼면 최대 ''M''개의 부분으로 ''n'' − ''M''의 분할이 생성된다.[1]

가우스 이항 계수는 다음과 같이 정의된다.

:{k+\ell \choose \ell}_q = {k+\ell \choose k}_q = \frac{\prod^{k+\ell}_{j=1}(1-q^j)}{\prod^{k}_{j=1}(1-q^j)\prod^{\ell}_{j=1}(1-q^j)}.

가우스 이항 계수는 다음 등식을 통해 ''p''(''N'', ''M''; ''n'')의 생성 함수와 관련이 있다.

:\sum^{MN}_{n=0}p(N,M;n)q^n = {M+N \choose M}_q.

6. 영 다이어그램과 영 격자



영 다이어그램은 자연수 분할을 시각적으로 표현하는 방법 중 하나로, 페러스 다이어그램이 점을 사용하는 것과 달리 상자를 사용한다. 이러한 표현 방식은 대칭 함수 및 군 표현론 연구에 유용하게 활용된다.[1] 영 다이어그램의 상자에 특정 규칙에 따라 숫자를 채워 넣으면 영 도표라는 객체가 만들어지는데, 이는 조합론 및 표현론적 의미를 갖는다.

영 다이어그램의 포함 관계는 부분 순서를 정의하며, 이 부분 순서 집합을 영 격자라고 한다. 영 격자는 대칭군의 기약 표현을 설명하는 데 사용되며, 미분 포셋의 예시로도 연구된다.

6. 1. 듀피 사각형

분할의 '''계수'''는 분할에서 최소한 크기 ''k''인 부분이 최소한 ''k''개 포함되는 가장 큰 수 ''k''를 의미한다. 예를 들어, 분할 4 + 3 + 3 + 2 + 1 + 1은 3개 이상의 부분이 3개 있지만, 4개 이상의 부분이 4개 있지는 않으므로 계수는 3이다. 계수 ''r''인 분할의 페러스 다이어그램 또는 영 다이어그램에서 왼쪽 상단의 ''r'' × ''r'' 크기의 사각형을 듀피 사각형이라고 한다.[1]



듀피 사각형은 다양한 분할 항등식의 증명과 같이 조합론 내에서 응용된다.[9] 또한 h-지수 형태로 실용적인 중요성을 갖는다.

참조

[1] 논문 Bijections between pattern-avoiding fillings of Young diagrams
[2] 저널 Partition identities - from Euler to the present http://www.maa.org/p[...]
[3] 문서 Notation follows Abramowitz Stegun
[4] 서적 Number Theory W. B. Saunders Company 1971
[5] 문서 Abramowitz Stegun
[6] 문서 Abramowitz Stegun
[7] 문서 Richard Stanley, Enumerative Combinatorics, volume 1, second edition. Cambridge University Press, 2012. Chapter 1, section 1.7.
[8] 서적 Some Famous Problems of the Theory of Numbers https://archive.org/[...] Clarendon Press 1920
[9] 문서 see, e.g., Stanley
[10] 서적 The surprising mathematics of longest increasing subsequences Cambridge University Press 2015
[11] 저널 Random matrices and random permutations 2000
[12] 저널 Infinite wedge and random partitions https://doi.org/10.1[...] 2001-04-01
[13] 문서 "[[伏見康治]]「[[確率論及統計論]]」第I章　数学的補助手段 1節 組合わせの理論 p.5 ISBN 9784874720127 http://ebsa.ism.ac.jp/ebooks/ebook/204"
[14] 문서 Andrews, George E. Number Theory. W. B. Saunders Company, Philadelphia, 1971. Dover edition, page 149–150.
[15] 저널 On an elementary proof of some asymptotic formulas in the theory of partitions 1942
[16] 서적
[17] 서적


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com