| <tableclass=grad> [[조합론|'''조합론 {{{#!wiki style="font-family: Times New Roman, serif; display: inline;"]] | ||
| {{{#!wiki style="min-height: calc(1.5em + 5px); margin: 0 -10px -5px" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#cb8a17,#ab7413><colcolor=#fff,#fff> 열거 조합론 | |
| 기초 | 경우의 수(공식) · 순열(직순열 · 중복 순열 · 동자 순열 · 원순열 · 동자 원순열 · 염주 순열 · 완전 순열) · 조합(중복조합) · 이항정리(이항계수 · 파스칼의 삼각형) | |
| 특수 | 분할(분할수) · 제1종 스털링 수 · 제2종 스털링 수 · 벨 수 · 라흐 수 · 오일러 수 · 카탈랑 수 | |
| 열거 기법·카운팅 | 포함-배제의 원리 · 더블 카운팅 · 비둘기 집의 원리 · 점화식 · 생성함수 | |
| 응용 조합론 | ||
| 그래프 이론 | 그래프 · 트리 · 인접행렬 · 한붓그리기 · 해밀턴 회로 · 기사의 여행 · 채색수와 채색다항식 · 4색정리 · 쌍대 그래프 · 쾨니히스베르크 다리 건너기 문제 · 리드 추측 · 로타 추측 | |
| 극값 조합론 | 램지 이론 | |
| 조합 설계론 | 라틴 방진 · 마방진(마법진) · 스도쿠 | |
| 기타 | 님 · 그린 타오 정리 · 여덟 퀸 문제 · 하노이의 탑 | |
| 틀:수학의 분과 · 틀:정수론 · 틀:이론 컴퓨터 과학 · 수학 관련 정보 | }}}}}}}}} | |
#!style
.grad {
background: border-box linear-gradient(to right, light-dark(#c18316, #a26e12), 10%, light-dark(#cb8a17, #ab7413) 50%, 90%, light-dark(#c18316, #a26e12));
border: 2px solid transparent;
}
.grad tr:nth-of-type(2) > td {
background: padding-box var(--article-background-color);
overflow: hidden;
}
1. 개요
Bell number1930년대 영국의 수학자 '에릭 템플 벨'의 이름에서 따온 것으로, 집합을 분할하는 방법의 수를 말한다. 원소의 개수가 [math(n)]인 집합을 분할하는 방법의 수를 [math(n)]번째 벨 수라고 하며 [math(B_n)]으로 나타낸다. 같은 표기의 베르누이 수와 혼동을 피하려면 사용 시에 정의를 명확히 해야 한다.[1]
제14항까지의 값은 다음과 같다. OEIS에 A000110 수열로 등록되어 있다.
| [math(n)] | [math(0)][2] | [math(1)] | [math(2)] | [math(3)] | [math(4)] | [math(5)] | [math(6)] | [math(7)] | [math(8)] | [math(9)] | [math(10)] | [math(11)] | [math(12)] | [math(13)] | [math(14)] |
| [math(B_n)] | [math(1)] | [math(1)] | [math(2)] | [math(5)] | [math(15)] | [math(52)] | [math(203)] | [math(877)] | [math(4140)] | [math(21147)] | [math(115975)] | [math(678570)] | [math(4213597)] | [math(27644437)] | [math(190899322)] |
2. 성질
- 제2종 스털링 수 [math(S(n,\,k))]와는 다음과 같은 관계가 있다.
[math(\displaystyle B_n = \sum_{k=0}^n S(n,\,k))]
집합론을 이용한 제2종 스털링 수의 정의가 ‘[math(n)]개의 원소로 구성된 집합을 [math(k)]개로 분할하는 경우의 수’이므로 위의 관계는 자명하다. - [math(B_n)]은 다음과 같은 점화식을 만족시킨다.
[math(\displaystyle B_{n+1} = \sum_{k=0}^n \binom nk B_k )]
집합 [math(\{1,\,2,\cdots\cdots,\,n+1\})]을 분할한다고 하자. 이때 각각의 분할에서 [math(1)]을 원소로 갖는 집합이 있을 것이다. [math(1)]을 원소로 갖는 집합의 원소의 개수가 [math(k)]가 되도록 분할하는 경우의 수는 [math(n)]개 중에서 [math(1)]을 제외한 [math((k-1))]개를 고르는 경우의 수 [math(\dbinom n{k-1})]에 나머지 [math(n-(k-1))]개의 원소를 분할하는 경우의 수 [math(B_{n-k+1})]를 곱한 값 [math(\dbinom n{k-1} B_{n-k+1})]임을 알 수 있다. [math(k)]는 [math(1)]부터 [math((n+1))]까지의 값을 취할 수 있고 [math(k)]가 다른 값을 취할 때 중복되는 경우는 없으므로 합의 법칙에 의해[math(\displaystyle B_{n+1}=\sum_{k=1}^{n+1}\binom n{k-1}B_{n-k+1} = \sum_{k=0}^n \binom nk B_{n-k} = \sum_{k=0}^n \binom n{n-k}B_k = \sum_{k=0}^n \binom nk B_k)]