분할 함수 계산기

조합론에서 가장 매혹적인 대상 중 하나인 분할을 탐구할 수 있는 모든 기능을 갖춘 분할 함수 계산기에 오신 것을 환영합니다. 비음의 정수 \(n\)을 입력하면 이 도구는 순서를 무시하고 \(n\)을 양의 정수의 합으로 나타내는 방법의 수인 \(p(n)\)과 함께, 서로 다른 부분의 분할 수 \(q(n)\), 홀수 부분의 분할 수 \(o(n)\), Hardy-Ramanujan 점근 추정치, 일치하는 모든 라마누잔 합동식을 계산하며, (작은 \(n\)의 경우) 모든 개별 분할을 애니메이션 Young 다이어그램으로 렌더링하여 보여줍니다.

분할 함수 p(n)이란 무엇입니까?

분할 함수 \(p(n)\)은 순서를 무시하고 \(n\)을 양의 정수의 합으로 나타내는 방법의 수를 셉니다. 더해지는 항들의 순서만 다른 두 합은 동일한 분할로 간주됩니다. 예를 들어, 4의 분할은 다음과 같습니다:

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

따라서 \(p(4) = 5\)가 됩니다. 관례상 \(p(0) = 1\)이며, 이는 "빈 분할"을 세는 것입니다. 몇 가지 추가 값: \(p(1) = 1,\ p(5) = 7,\ p(10) = 42,\ p(50) = 204{,}226,\ p(100) = 190{,}569{,}292.\)

생성 함수

레온하르트 오일러는 \(p(n)\)의 생성 함수가 다음과 같이 아름답고 간결한 곱의 형태를 가진다는 것을 발견했습니다:

각 인수 \(1/(1 - x^k) = 1 + x^k + x^{2k} + \ldots\)는 분할에서 부분 \(k\)가 몇 번 나타나는지를 선택하는 데 기여합니다. 이 인수들을 모두 곱하면 모든 분할이 정확히 한 번씩 생성됩니다.

Young (Ferrers) 다이어그램

Young 다이어그램(Ferrers 다이어그램이라고도 함)은 분할을 왼쪽 정렬된 상자 배열로 시각화하여 나타냅니다. 각 행은 하나의 분할 부분에 해당하며, 행은 큰 것부터 작은 것 순으로 나열됩니다. 예를 들어, 7의 분할인 \(4 + 2 + 1\)은 다음과 같이 표현됩니다:

Young 다이어그램을 통해 분할 항등식을 "눈으로 확인"할 수 있습니다. 다이어그램을 주대각선을 기준으로 대칭 이동하면 행이 열이 되며, 이는 켤레 분할(conjugate partition)에 해당합니다. 이 계산기는 \(n \le 15\)인 경우 \(n\)의 모든 분할에 대해 Young 다이어그램을 렌더링합니다.

오일러의 분할 정리

오일러의 가장 우아한 결과 중 하나는 다음과 같습니다:

예를 들어, 7을 서로 다른 부분으로 분할하면 \(\{7\}, \{6+1\}, \{5+2\}, \{4+3\}, \{4+2+1\}\)로 총 5개입니다. 7을 홀수 부분으로 분할하면 \(\{7\}, \{5+1+1\}, \{3+3+1\}, \{3+1+1+1+1\}, \{1+1+1+1+1+1+1\}\)로 역시 5개입니다. 계산기의 요약 패널은 \(q(n)\)과 \(o(n)\)을 모두 보고하므로 선택한 \(n\)에 대해 이 항등식을 확인할 수 있습니다.

Hardy-Ramanujan 점근 공식

1918년, G.H. Hardy와 Srinivasa Ramanujan은 큰 \(n\)에 대한 \(p(n)\)의 실제 성장 속도를 포착한 최초의 공식을 증명했습니다.

이 결과는 단위 원 위의 특이점 주변에서 생성 함수를 적분하는 Hardy-Ramanujan 원법(circle method)에서 도출되었습니다. Hans Rademacher는 1937년에 이를 정확한 수렴 급수로 다듬었으며, 이는 해석적 정수론에서 가장 유명한 공식 중 하나입니다.

라마누잔 분할 합동식

라마누잔은 분할 값 표를 연구하던 중 세 가지 놀라운 가해성 패턴을 발견했습니다.

예를 들어, \(p(4)=5,\ p(9)=30,\ p(14)=135,\ p(19)=490,\ p(24)=1575\)는 모두 5의 배수입니다. 계산기는 사용자가 선택한 \(n\)이 이들 클래스 중 하나에 해당할 때 자동으로 표시해 줍니다.

이 계산기 사용 방법

1. 입력란에 500 이하의 비음의 정수를 입력하거나 유명한 퀵 예제(0, 4, 10, 42, 100, 200) 중 하나를 클릭하세요.
2. "분할 계산하기"를 클릭합니다. 도구가 \(p(n)\), \(q(n)\), \(o(n)\) 및 Hardy-Ramanujan 추정치를 계산합니다.
3. 큰 헤드라인 숫자로 \(p(n)\)을 보여주는 히어로 패널을 확인한 다음, 요약 그리드에서 서로 다른 부분, 홀수 부분, 점근 추정치 및 백분율 오차를 훑어보세요.
4. Young 다이어그램 검토 — \(n \le 15\)인 경우, 반응형 그리드에 모든 개별 분할이 애니메이션 Young 다이어그램으로 그려집니다.
5. 성장 차트 탐색 — \(k = 0, 1, \ldots, n\)에 대해 \(p(k)\), \(q(k)\) 및 Hardy-Ramanujan 곡선을 도표로 보여줍니다. 선형 스케일과 로그 스케일 사이를 전환하여 점근적 형태를 확인하세요.
6. 성장 표 읽기 — 작은 \(k\)에 대한 \(p(k), q(k), o(k)\)를 한 줄씩 보여줍니다. 각 라마누잔 합동식이 처음 발생하는 지점을 찾는 데 활용해 보세요.

계산 예시: 5의 분할

\(n = 5\)인 경우를 살펴봅시다. 모든 분할은 다음과 같습니다:

• \(5\)
• \(4 + 1\)
• \(3 + 2\)
• \(3 + 1 + 1\)
• \(2 + 2 + 1\)
• \(2 + 1 + 1 + 1\)
• \(1 + 1 + 1 + 1 + 1\)

따라서 \(p(5) = 7\)입니다. 서로 다른 부분으로의 분할: \(\{5\}, \{4+1\}, \{3+2\}\)로 3개이므로 \(q(5) = 3\)입니다. 홀수 부분으로의 분할: \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\)로 역시 3개이므로 \(o(5) = 3\)입니다. 오일러의 정리가 성립함을 알 수 있습니다. 마지막으로 \(n = 5 \equiv 0 \pmod 5\)는 \(5k+4\) 형태가 아니므로 5-합동식이 적용되지 않지만, \(p(4) = 5\)는 \(p(5k+4) \equiv 0 \pmod 5\)를 만족합니다.

p(n)의 대표적인 값들

역사

• 1750년대: 레온하르트 오일러가 분할을 연구하고 생성 함수 항등식과 "서로 다른 부분 = 홀수 부분" 정리를 발견합니다.
• 1915년: Percy MacMahon 소령이 \(n\) 최대 200까지의 \(p(n)\) 표를 발표합니다 — 수작업으로 계산되었습니다.
• 1918년: Hardy와 Ramanujan이 원법을 사용하여 점근 공식을 증명합니다.
• 1919년: Ramanujan이 유명한 합동식 \(p(5k+4),\ p(7k+5),\ p(11k+6)\)을 발표합니다.
• 1937년: Hans Rademacher가 Hardy-Ramanujan 공식을 정확한 수렴 급수로 개선합니다.
• 2011년: Ken Ono와 Jan Bruinier가 모든 양의 정수에서 \(p(n)\)이 유한한 대수적 합으로 표현될 수 있음을 증명합니다.

응용 분야

• 조합론 및 표현론 — 분할은 대칭군 \(S_n\)의 기약 표현을 인덱싱합니다.
• 통계 역학 — 분할 수는 이상 양자 기체의 엔트로피와 끈 이론 분할 함수에 나타납니다.
• 모듈러 형식 — \(p(n)\)의 생성 함수는 데데킨트 에타 함수와 밀접한 관련이 있습니다.
• 컴퓨터 과학 — 부분 집합 합 문제(subset-sum) 및 정수 계획법 열거 벤치마크에서 분할 수가 빈번하게 사용됩니다.

자주 묻는 질문

분할 함수 p(n)이란 무엇입니까?

\(p(n)\)은 순서를 고려하지 않고 \(n\)을 양의 정수의 합으로 표현하는 방법의 수입니다. \(p(4) = 5\)인 이유는 4를 \(4\), \(3+1\), \(2+2\), \(2+1+1\), \(1+1+1+1\)로 쓸 수 있기 때문입니다. 관례상 \(p(0) = 1\)입니다.

Young 또는 Ferrers 다이어그램이란 무엇입니까?

Young 다이어그램은 분할을 시각적으로 나타낸 것입니다. 각 부분은 왼쪽 정렬된 상자 행이 되며, 부분은 위에서 아래로 가장 큰 것부터 작은 것 순으로 나열됩니다. \(4+2+1\)의 경우, 4개, 2개, 1개 상자의 행을 그립니다. 이 계산기는 \(n \le 15\)일 때 모든 분할에 대해 Young 다이어그램을 렌더링합니다.

오일러의 분할 정리는 무엇을 말합니까?

모든 양의 정수 \(n\)에 대하여, \(n\)을 서로 다른 부분으로 분할하는 방법의 수는 \(n\)을 홀수 부분으로 분할하는 방법의 수와 같습니다. \(n = 5\)의 경우: 서로 다른 부분은 \(\{5\}, \{4+1\}, \{3+2\}\)이며, 홀수 부분은 \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\)입니다. 두 경우 모두 3개로 동일합니다.

Hardy-Ramanujan 점근 공식이란 무엇입니까?

\(n \to \infty\)일 때 \(p(n) \sim \frac{1}{4n\sqrt{3}} \exp\!\left( \pi \sqrt{2n/3} \right)\)임을 나타내는 공식입니다. 이는 1918년 G.H. Hardy와 Srinivasa Ramanujan에 의해 발견된, \(p(n)\)의 정확한 성장 속도를 설명하는 최초의 공식이었습니다.

라마누잔 분할 합동식이란 무엇입니까?

세 가지 놀라운 가해성 패턴인 \(p(5k+4) \equiv 0 \pmod 5\), \(p(7k+5) \equiv 0 \pmod 7\), \(p(11k+6) \equiv 0 \pmod{11}\)을 말합니다. 예를 들어 \(p(4)=5, p(9)=30, p(14)=135\)는 모두 5의 배수입니다.

p(n)은 얼마나 빨리 증가합니까?

p(n)은 지수함수보다 약간 느리지만 어떤 다항식보다 빠르게 증가하며, 대략 \(\exp(\pi \sqrt{2n/3})\)의 속도로 증가합니다. 비교하자면 \(p(10)=42\), \(p(50)=204{,}226\), \(p(100)=190{,}569{,}292\), \(p(200) \approx 4 \times 10^{12}\)입니다. 차트의 로그 스케일 전환을 사용하여 이 성장 곡선을 시각화해 보세요.

추가 리소스

• 분할 함수 - Wikipedia (영문)
• 라마누잔 합동식 - Wikipedia (영문)