, 초등교육에서의 분할에 대한 내용은 가르기 문서
참고하십시오.| 이산수학 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. 개요
조합과 관련된 내용이다. 분할에는 자연수의 분할과 집합의 분할이 있다. 한마디로 자연수와 집합을 조합을 이용해 나누는 방법.2. 종류
2.1. 자연수의 분할
자연수 [math(n)]을 [math(r)]개의 자연수의 합으로 나타내는 가짓수를 [math(p\left(n,\ r\right))]로 표기한다. 단, [math(1 \le r \le n)]이다. [1] 이때 순서는 생각하지 않는다. 예를 들어 [math(5)]를 [math(3)]개의 자연수로 나누면 [math(5=3+1+1=2+2+1)] 이므로 [math(p\left(5,\ 3\right)=2)] 이다.모든 경우를 다 합친 것은 [math(\displaystyle \sum_{k=1}^n p\left(n,\ k \right) = p_n)]으로 표기하는데, 이를 분할수라고 부른다.
2.1.1. 성질
[math(p\left(n,\ 2 \right) = \biggl\lfloor \dfrac n2 \biggr\rfloor)], [math(p\left(n,\ 3 \right) = {\rm round}\left( \dfrac{n^2}{12} \right))]단, 여기서 [math(\lfloor x \rfloor)]는 [math(x)]를 넘지 않는 최대정수이고 [math({\rm round}(x))]는 [math(x)]를 반올림[2]한 것이다.
2.1.2. 분할수
자연수 [math(n)]을 분할하는 방법의 수를 분할수라고 한다. 따라서 분할수는 [math(p\left(n,\ k\right))]들의 합으로 나타내어진다.2.1.3. 켤레 분할
[math((3,\ 2,\ 2))], [math((3,\ 3,\ 1))]과 같이 서로가 서로의 '[math(k)] 이상의 자연수 개수'를 나타내는 두 분할의 관계를 켤레 분할(conjugate partition) 또는 공액 분할이라고 한다. 즉 [math((3,\ 2,\ 2))]에서는 [math(1)] 이상인 자연수의 개수가 [math(3)]개, [math(2)] 이상인 자연수의 개수가 [math(3)]개, [math(3)] 이상인 자연수의 개수가 [math(1)]개이므로 [math((3,\ 2,\ 2))]의 켤레 분할이 [math((3,\ 3,\ 1))]이 되고, 같은 방법으로 따지면 그 반대 관계도 성립한다. 이는 분할의 개수대로 가로로 블록을 쌓고 세로로 블록 수를 세어서 새로운 분할을 얻는 것과 같으므로, 켤레 분할은 일대일 대응이다.2.2. 집합의 분할
제2종 스털링 수 (Stirling numbers of the second kind)원소가 [math(n)]개인 집합을 [math(r)]개의 공집합이 아니면서 서로소인 부분집합들의 합집합으로 나타내는 가짓수를 [math(S\left(n,\ r\right))]로 표기한다.[3] 예를 들어 [math(\left\{1,\ 2,\ 3\right\})]을 [math(2)]개의 부분집합들로 나누면 [math(\left\{1,\ 2\right\}\cup\left\{3\right\}=\left\{1,\ 3\right\}\cup\left\{2\right\}=\left\{2,\ 3\right\}\cup\left\{1\right\})]이므로 [math(S\left(3,\ 2\right)=3)] 이다.
2.2.1. 성질
- [math(S \left( n,\ k \right) = S \left( n-1,\ k-1 \right) + k \times S \left( n-1,\ k \right) )]
- [math(S \left( n,\ 2 \right) = 2^{n-1} -1 )]
- [math(S \left( n,\ 3 \right) = \frac{1}{3!} \times (3^n -3 \times 2^n +3) )]
- [math(S \left( n,\ n-1 \right) = \displaystyle \binom{n}{2}=\frac{n(n-1)}{2} )] [4]
2.2.2. 벨 수
원소의 개수가 [math(n)]인 집합을 분할하는 방법의 수를 벨 수라고 한다. 따라서 벨 수는 [math(S\left(n,\ k\right))]들의 합으로 나타내어진다.3. 여담
- 대한민국의 고등학교 수학 교과목에는 제7차 교육과정에서 이산수학에 있었다가 2007 개정 교육과정에서 아예 삭제되었고, 2009 개정 교육과정에서 확률과 통계 과목에서 다시 등장하였다가 2015 개정 교육과정(문·이과 통폐합 교육과정)에서부터 재삭제된다.
4. 관련 문서
[1] 대문자로 나타내기도 한다. [math(P\left(n,\ r\right))][2] 언뜻 반올림한 값이 참이라는 데에 의문이 들 수 있다.[3] 집합론으로 정의하면 [math(1 \le r \le n)]이지만 대수적으로도 엄밀하게 정의할 수 있기 때문에 [math(r)], [math(n)]은 정수이기만 하면 된다. 물론 [math(n<r)]이면 [math(S \left( n,\ r \right) = 0)]이다.[4] [math( \displaystyle \binom{n}{2})]는 조합 기호로, 고교 과정에서는 [math({}_n\mathrm C_2)]라 쓴다.