|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
分 割 數 / partition number, number of partitions자연수 n을 분할하는 방법의 수, 즉 순서를 고려하지 않고 1개 이상의 자연수의 합으로 표시하는 방법의 수를 분할수라고 한다. [math(P_n)] 또는 [math(p(n))] 으로 표기한다.
2. 예시
예를 들어 n = 4 인 경우는|
4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 |
n = 5 인 경우는
|
5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 |
n 을 k 개의 수로 분할하는 방법을 p(n,k)로 표기하므로, 아래 식으로 쓸 수 있다.
[math(\displaystyle {P}_{n} = \sum_{k=1}^{n}p\left(n ,k \right) )]
p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7 이며, 여기서 분할수의 목록을 확인할 수 있다.
참고로 편의상 p(0) = 1 로 둔다.
한편 n의 분할 중 원소가 중복되지 않는 수, 즉 덧셈식에서 각 수가 한 번만 나오는 경우의 수를 나타내는 수열도 있다. 이를 위키백과에서는 q(n)이라고 하며, 여기서 그 수열을 확인할 수 있다. q(n) 표현을 빌리자면 q(1)=q(2)=1, q(3)=q(4)=2, q(5)=3이며, q(0) 역시 편의상 1로 표기한다.
예를 들어 q(4)를 구하자면, 앞에서 구한 4의 분할들 중 덧셈식에서 각 수가 한 번만 나오는 경우는 4, 3+1의 2가지이므로 q(4)=2이다. 마찬가지로 q(5)를 구하면 경우의 수는 5, 4+1, 3+2의 3이므로 q(5)=3이다.
q(n)은 n을 홀수만 사용해서 분할하는 방법의 수와 같다는 사실이 알려져 있다.
3. 구하는 방법
수가 작으면 하나하나 손으로 분할을 나열해도 되겠지만 좀만 커져도 힘들다. 보통은 분할수의 생성함수를 이용해 다음처럼 계산한다. 약간의 조합론 지식이 있으면, 생성함수가 다음처럼 나타난다는 것을 바로 알 수 있다.
[math( \displaystyle P(x) = \sum_{n=0}^{\infty} p(n) x^n = \prod_{i=1}^{\infty} \frac{1}{1- x^i} )]
이 생성함수에 대해서 다음의
오일러의 오각수[1] 공식 (pentagonal number formula)을 증명할 수 있다.
[math( \displaystyle P(x)^{-1} = 1 + \sum_{k=1}^{\infty} (-1)^k \left( x^{k(3k+1)/2} + x^{k(3k-1)/2} \right) )]
이름의 유래는 [math(k(3k \pm 1)/2)]들이 오각수라서이다. 근데 이게 그냥 나온 게 아니라, 이 공식을 증명할 때 실제로 오각수 모양의 분할 배열(페러스 다이어그램)이 중요하게 사용된다. 꽤나 신기하고 아름다운 조합적 증명이니 관심있으면 조합론 기본교재에서 찾아 읽어보자. 하여튼간 이걸 이용하면 다음의 점화식을 얻을 수 있다. ([math(k<0)]이면 [math(p(k)=0)]으로 간주)
[math( \displaystyle p(n) = \sum_{k = 1}^{\infty} (-1)^{k+1} \left( p(n - \frac{k(3k+1)}{2}) + p (n - \frac{k(3k-1)}{2}) \right) )]
이게 컴퓨터로 계산할 때 복잡도 [math(O(n^2))]으로 해결할 수 있는 그나마 간단한 식이다.분할수의 정확한 공식으로는 하디-라마누잔-라데마커 공식이 있는데, 하디와 라마누잔이 맨 처음 얻어낸 근사식
[math(\displaystyle p(n) \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt {\frac{2n}3} \right) )]
을 라데마커와 보완하여 만든 다음의 공식이다.
[math( \displaystyle p(n) = {\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty}A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\exp \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right) )] [2]
물론 실전에서 이걸 써서 분할수를 계산하지는 않는다. 영화 무한대를 본 남자에 이 공식에 대한 에피소드가 등장한다. 라마누잔의 증명과정 없는 정리 때문에, 라마누잔의 업적이 수학계에 인정받지 못한다. 하디는 그런 라마누잔을 돕기 위해서, 분할수의 대가인 라데마커를 끌어 들여 라마누잔의 분할수 공식이 상당히 정확하다는 점을 인정받게 한다.
중복되는 원소가 없는 분할수 q(n) 역시 근삿값에 대한 다음 공식이 있다.
[math(\displaystyle q(n) \sim { { e^{\pi \sqrt {\frac{n}3} }} \over {4\sqrt[4]{3n^3}} })]
비슷하게 오일러의 오각수 공식을 이용해서 점화식을 끌어낼 수도 있다.4. 관련 문서
[1]
삼각수처럼 오각형 안에 점을 배열했을 때의 점의 개수
[2]
단 [math( \displaystyle A_{k}(n)=\sum _{0 \leq m<k,\;(m,k)=1}e^{\pi i\left(s(m,k)-2nm/k \right)} )], [math( \displaystyle s(m,k) = \sum_{l \mod k} (\!( \frac{l}{k} )\!) (\!( \frac{ml}{k} )\!) )] 데데킨트 합