본문 바로가기
영문 위키피디아 번역

(번역) Integer partition

by 다움위키 2024. 3. 16.
Original article: w:Integer partition

 

숫자 이론(number theory) 및 조합론(combinatorics)에서, 역시 정수 분할(integer partition)로 불리는, 양의 정수(integer) n의 분할(partition)은 n을 양의 정수의 합(sum)으로 쓰는 방법입니다. 오직 그들 합해지는-숫자(summand)의 순서에서 다른 두 합은 같은 분할로 여겨집니다. (만약 순서가 중요하면, 합은 합성(composition)이 됩니다.) 예를 들어 4는 다음의 다섯 구별되는 방법에서 분할될 수 있습니다:

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

순서-종속적인 합성(composition) 1 + 3은 3 + 1과 같은 분할이지만, 두 구별되는 합성 1 + 2 + 1과 1 + 1 + 2은 2 + 1 + 1과 같은 분할을 나타냅니다.

분할에서 합해지는-숫자는 부분(part)으로 역시 불립니다. n의 분할의 숫자는 분할 함수 p(n)에 의해 제공됩니다. 그래서 p(4) = 5입니다. 표기법 λ ⊢ n은 λ가 n의 분할임을 의미합니다.

분할은 영 다이어그램(Young diagram) 또는 퍼얼스 다이어그램(Ferrers diagram)과 함께 그래픽적으로 시각화될 수 있습니다. 그들은 일반적으로 대칭 다항식(symmetric polynomial), 대칭 그룹(symmetric group) 및 그룹 표시 이론(group representation theory)의 연구를 포함하여 수학(mathematics) 및 물리학(physics)의 많은 가지에서 발생합니다.

Examples

5의 7 분할은 다음입니다:

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

일부 교재에서, 분할은 더하기 기호를 갖는 표현이 아니라 더해지는-숫자의 수열로 취급됩니다. 예를 들어, 분할 2 + 2 + 1은 튜플 (2, 2, 1) 또는 훨씬 더 간결한 형식 (22, 1)으로 대신 쓰일 수 있으며, 여기서 위첨자는 항의 반복 횟수를 나타냅니다.

Representations of partitions

분할을 나타내는 두 가지 공통적인 다이어그램 방법이 있습니다: 그것은 노먼 매클라우드 퍼얼스(Norman Macleod Ferrers)의 이름을 따서 지은 퍼얼스 다이어그램, 및 영국의 수학자 알프레드 영(Alfred Young)의 이름을 따서 지은 영 다이어그램입니다. 둘 다는 여러 가지 가능한 관례가 있습니다; 여기서, 우리는 위-왼쪽 구석에 다이어그램을 정렬하는 영어 표기법(English notation)을 사용합니다.

Ferrers diagram

양의 숫자 14의 분할 6 + 4 + 3 + 1은 다음 다이어그램에 의해 표현될 수 있습니다:

14개 원은 각 행이 분할의 부분의 크기를 가진 4개의 행으로 정렬되어 있습니다. 숫자 4의 5 분할에 대해 다이어그램은 아래에 목록화되어 있습니다:

Young diagram

정수 분할의 대안적인 시각적 표현은 영 다이어그램(Young diagram)입니다 (역시 퍼얼스 다이어그램으로 종종 불립니다). 퍼얼스 다이어그램에서 처럼, 점과 함께 분할을 표현하는 것이 아니라, 영 다이어그램은 상자 또는 사각형을 사용합니다. 따라서, 분할 5 + 4 + 1에 대해 영 다이어그램은 다음입니다:

반면에 같은 분할에 대해 퍼얼스 다이어그램은 다음입니다:

이 겉으로 보기에 자명한 변화가 별도로 언급할만한 가치가 있어 보이지 않는 반면에, 영 다이어그램은 대칭 함수(symmetric functions) 및 그룹 표시 이론(group representation theory)의 연구에서 매우 유용함이 밝혀집니다: 다양한 규칙을 지키는 숫자 (또는 때때로 보다 복잡한 대상)을 갖는 영 다이어그램의 상자를 채우는 것은 영 타블로(Young tableaux)로 불리는 대상의 가족을 이어지고, 이들 타블로는 조합론적 및 표시-이론적 중요성을 가집니다. 함께 어울려 인접한 사각형에 의해 만들어진 유형에서 처럼, 영 다이어그램은 폴리오미노(polyomino)의 특별한 종류입니다.

Partition function

분할 함수(partition function) \(\displaystyle p(n)\)은 비-음의 정수 \(\displaystyle n\)의 가능한 분할(partitions)의 숫자(number)를 나타냅니다. 예를 들어, \(\displaystyle p(4)=5\)인데 왜냐하면 정수 \(\displaystyle 4\)는 다섯 분할 \(\displaystyle 1+1+1+1\), \(\displaystyle 1+1+2\), \(\displaystyle 1+3\), \(\displaystyle 2+2\), 및 \(\displaystyle 4\)를 가집니다.

\(\displaystyle n=0,1,2,\dots\)에 대해 이 함수의 값은 다음입니다:

  • 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (OEIS에서 수열 A000041).

분할 함수에 대해 닫힌-형식 표현(closed-form expression)은 알려져 있지 않지만, 그것은 정확하게 근사하는 점근 전개(asymptotic expansions) 및 그것이 정확하게 계산될 수 있는 재귀 관계(recurrence relation) 둘 다를 가집니다. 그것은 논증의 제곱근(square root)의 지수 함수(exponential function)로 증가합니다. 그것의 생성하는 함수(generating function)의 곱셈의 역(multiplicative inverse)은 오일러 함수(Euler function)입니다; 오일러의 오각 숫자 정리(pentagonal number theorem)에 의해, 이 함수는 그 인수의 오각 숫자(pentagonal number) 거듭-제곱의 교대하는 합입니다.

스리미바자 라마누젠(Srinivasa Ramanujan)은 먼저 분할 함수가 모듈러 산술(modular arithmetic)에서 비-자명한 패턴을 가지고 있음을 발견했으며, 지금 라마누젠의 합동(Ramanujan's congruences)으로 알려져 있습니다. 예를 들어, \(\displaystyle n\)의 십진수 표시가 자릿수 4 또는 9로 끝날 때마다, \(\displaystyle n\)의 파티션의 숫자는 5로 나누어질 것입니다.

Restricted partitions

조합론과 숫자 이론 둘 다에서, 다양한 제한을 받는 분할의 가족이 종종 연구됩니다. 이 섹션은 몇 개의 그러한 제한을 조사합니다.

Conjugate and self-conjugate partitions

만약 우리가 그의 주요 대각선을 따라 분할 6 + 4 + 3 + 1의 그림을 뒤집으면, 우리는 14의 또 다른 분할을 얻습니다:

행을 열로 바꿈으로써, 우리는 숫자 14의 분할 4 + 3 + 3 + 2 + 1 + 1을 얻습니다. 그러한 분할은 서로의 켤레로 말합니다. 숫자 4의 경우에서, 분할 4 및 1 + 1 + 1 + 1은 켤레 쌍이고, 분할 3 + 1 및 2 + 1 + 1은 서로의 켤레입니다. 물론 흥미는 분할 2 + 2이며, 이것은 켤레로 자신을 가집니다. 그러한 분할은 자기-켤레로 말합니다.

 

주장: 자체-켤레 분할의 숫자는 구별하는 홀수 부분을 갖는 분할의 숫자와 같습니다.

증명 (개요): 치명적인 관찰은 모든 각 홀수 부분이 자기-켤레 다이어그램을 형성하기 위해 중간에서 "접힐" 수 있다는 것입니다.

우리는 그런-다음, 다음 예제에서 묘사된 것처럼, 구별되는 홀수 부분을 갖는 분할의 집합과 자체-켤레 분할의 집합 사이의 전단사를 얻을 수 있습니다:

Odd parts and distinct parts

숫자 8의 22 분할 사이에, 오직 홀수 부분을 포함하는 6가 있습니다:

  • 7 + 1
  • 5 + 3
  • 5 + 1 + 1 + 1
  • 3 + 3 + 1 + 1
  • 3 + 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

대안적으로, 우리는 숫자가 한 번보다 많이 발생하는 않는 분할을 셀 수 있습니다. 그러한 분할은 구별되는 부분을 갖는 분할로 불립니다. 만약 우리가 구별되는 부분을 갖는 8의 분할을 세면, 우리는 역시 6을 얻습니다:

  • 8
  • 7 + 1
  • 6 + 2
  • 5 + 3
  • 5 + 2 + 1
  • 4 + 3 + 1

이것은 일반적인 속성입니다. 각 양수에 대해, 홀수 부분을 갖는 분할의 숫자는 q(n)으로 표시되는 구별되는 부분을 갖는 분할의 숫자와 같습니다. 이 결과는 1748년에 레온하르트 오일러(Leonhard Euler)에 의해 입증되었고 나중에 글레이셔의 정리(Glaisher's theorem)로 일반화되었습니다.

모든 제한된 분할의 모든 각 유형에 대해, 주어진 제한을 만족시키는 분할의 숫자에 대해 해당하는 함수가 있습니다. 중요한 예제는 q(n)입니다. q(n)의 처음 몇 개의 값은 (q(0)=1로 시작하여) 다음입니다:

  • 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (OEIS에서 수열 A000009).

q(n)에 대해 생성하는 함수(generating function) (구별되는 부분으로 분할)는 다음에 의해 제공됩니다:

\(\quad\displaystyle \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}} .\)

오각 숫자 정리(pentagonal number theorem)는 q에 대해 재귀를 제공합니다:

\(\quad 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=3m^2-m\)이면 \((-1)^m\)이고 그렇지 않으면 0입니다.

Restricted part size or number of parts

켤레를 취함으로써, n의 정확히 k 부분으로 나누는 분할의 숫자 \(p_k(n)\)는 가장 큰 부분이 크기 k인 n의 분할의 숫자와 같습니다. 함수 \(p_k(n)\)는 다음 재귀를 만족시킵니다:

\(\quad p_k(n) = p_k(n-k)+p_{k-1}(n-1)\)

이때 초기 값은 \(p_0(0)=1\)이고 만약 n ≤ 0 또는 k ≤ 0이고 n 및 k이 둘 다 영이 아니면 \(p_k(n)=0\)입니다.

우리는 다음에 의해 함수 p(n)을 다시-덮습니다:

\(\quad\displaystyle 
p(n) = \sum_{k = 1}^n p_k(n).
\)

고정된 k와 n 변수를 취하는, 그러한 분할에 대해 하나의 가능한 생성하는 함수는 다음입니다:

\(\quad\displaystyle  \sum_{n \geq 0} p_k(n) x^n = x^k \cdot \prod_{i = 1}^k \frac{1}{1 - x^i}.\)

보다 일반적으로, 만약 T가 양의 정수의 집합이면 n의 분할의 숫자는, 그의 부분의 모두가 T에 속하는, 다음 생성하는 함수(generating function)를 가집니다:

\(\quad\displaystyle \prod_{t \in T}(1-x^t)^{-1}.\)

이것은 변화-만들기 문제(change-making problem)를 해결하기 위해 사용될 수 있습니다 (여기서 집합 T는 이용-가능한 동전을 지정합니다). 두 가지 특별한 경우로서, 우리는 모든 부분이 1 또는 2인 n의 분할의 숫자 (또는, 동등하게, n을 1 또는 2 부분로의 분할의 숫자)는 다음임을 가집니다:

\(\quad\displaystyle \left \lfloor \frac {n}{2}+1 \right \rfloor ,\)

그리고 모든 부분이 1, 2 또는 3인 n의 분할의 숫자 (또는, 동등하게, n을 최대 세 부분으로의 분할의 숫자)는 \((n+3)^2/12\)에 가장-가까운 정수입니다.

Asymptotics

p(n)에 대해 점근 증가 비율(asymptotic growth rate)은 다음에 의해 제공됩니다:

\(\quad\displaystyle  \log p(n) \sim C \sqrt n \text { as } n\rightarrow \infty\)

여기서 \(\displaystyle C = \pi\sqrt\frac23\)입니다.

만약 A가 자연수의 집합이면, 우리는 \(p_A(n)\)를 n을 A의 원소로 나누는 분할의 숫자를 나타내는 것으로 놓습니다. 만약 A가 양의 자연 밀도(natural density) α를 소유하면 다음이고

\(\quad\displaystyle  \log p_A(n) \sim C \sqrt{\alpha n}  \)

거꾸로 만약 이것 점근 속성이 \(p_A(n)\)에 대해 유지되면 A는 자연 밀도 α를 가집니다. 이 결과는 1942년에 에르되시(Erdős)에 의해 증명의 스케치와 함께 언급되었습니다.

만약 A가 유한 집합이면, 이 해석은 적용되지 않습니다 (유한 집합의 밀도는 영입니다). 만약 A가 그의 최대 공통 약수가 1인 k 원소를 가지면, 다음입니다:

\(\quad\displaystyle  p_A(n) = \left(\prod_{a \in A} a^{-1}\right) \cdot \frac{n^{k-1}}{(k-1)!} + O(n^{k-2}) . \)

Partitions in a rectangle and Gaussian binomial coefficients

우리는 부분의 숫자와 크기를 동시에 역시 극한할 수 있습니다. p(N, M; n)은 각각 최대 M 부분, 최대 N 크기의 각각을 갖는 n의 분할의 숫자를 나타내는 것으로 놓습니다. 동등하게, 이들은 그의 영 다이어그램이 M × N 사각형 안에 맞는 분할입니다. \(\displaystyle p(N,M;n) - p(N,M-1;n)\)이 n을 크기 최대 N의 정확하게 M 부분으로의 분할을 세고, 그러한 분할의 각 부분으로부터 1을 빼면 n − M을 최대 M 부분으로의 분할을 산출하는 것을 관찰함으로써 얻어지는 다음 재귀 관계가 있습니다:

\(\quad\displaystyle p(N,M;n) = p(N,M-1;n) + p(N-1,M;n-M) \).

가우스 이항 계수(Gaussian binomial coefficient)는 다음으로 정의됩니다:

\(\quad\displaystyle {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)의 생성하는 함수(generating function)와 관련됩니다:

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

Rank and Durfee square

분할의 랭크는 분할이 크기 적어도 k의 적어도 k 부분을 포함하도록 가장-큰 숫자 k입니다. 예를 들어, 분할 4 + 3 + 3 + 2 + 1 + 1은 랭크 3을 가지는데 왜냐하면 그것은 ≥ 3인 3 부분을 포함하지만,  ≥ 4인 4 부분을 포함하지 않기 때문입니다. 랭크 r의 분할의 페러스 다이어그램 또는 영 다이어그램에서, 위-왼쪽에서 엔트리의 r x r 정사각형은 더피 정사각형(Durfee square)으로 알려져 있습니다:

더피 정사각형은 분할 항등식의 증명에서 조합론 안에서 응용을 가집니다. 그것은 역시 h-인덱스(h-index)의 형식에서 실질적인 의미를 가집니다.

다른 통계량은 분할의 랭크(rank of a partition) (또는 다이슨 랭크), 즉, 가장 큰 부분 \(\displaystyle \lambda_k\)을 갖는 k 부분의 분할에 대해 차이 \(\displaystyle \lambda_k - k\)로 때때로 불립니다. 이 통계량 (이것은 위에서 설명된 하나의 관련이 없음)는 라마누젠 합동(Ramanujan congruences)의 연구에서 나타납니다.

Young's lattice

영 다이어그램의 포함에 의해 주어진 분할에 대한 자연스러운 부분 순서(partial order)가 있습니다. 이 부분적으로 순서화 집합은 영의 격자(Young's lattice)로 알려져 있습니다. 격자는 표시 이론(representation theory)의 문맥에서 원래 정의되었으며, 여기서 그것은, 특성 영에서, 그들의 분기하는 속성과 함께 모든 n에 대해 대칭 그룹(symmetric group) \(S_n\)의 기약 표시(irreducible representation)를 묘사하기 위해 사용됩니다. 그것은 역시 순전히 조합론적 속성에 대해 중요한 연구를 받아 왔습니다; 특히, 그것은 차이 포셋(differential poset)의 동기-부여 예제입니다.

See also

 

 

References

External links

 

관련글

티스토리툴바