벨 수

 


1. 개요
2. 성질
3. 관련 문서

Bell number

1. 개요

집합을 분할하는 방법의 수로, 원소의 개수가 $$n$$인 집합을 분할하는 방법의 수를 $$n$$번째 벨 수라고 하며 $$B_n$$으로 나타낸다. 베르누이 수와 표기가 완전히 같기 때문에, 혼동을 피하기 위해 사용시에는 정의를 명확히 해줄 필요가 있다.
1930년대 이를 연구한 영국의 수학자 에릭 템플 벨의 이름을 따왔다.
제9항까지의 값은 다음과 같다.
$$n$$
[math(0)][1]
$$1$$
$$2$$
$$3$$
$$4$$
$$5$$
$$6$$
$$7$$
$$8$$
$$9$$
$$B_n$$
$$1$$
$$1$$
$$2$$
$$5$$
$$15$$
$$52$$
$$203$$
$$877$$
$$4140$$
$$21147$$

2. 성질

$$\displaystyle B_n = \sum_{k=0}^n S \left( n,~k \right)$$
집합론을 이용한 제2종 스털링 수의 정의가 ‘$$n$$개의 원소로 구성된 집합을 $$k$$개로 분할하는 경우의 수’이므로 위의 관계는 자명하다.
  • $$B_n $$은 다음과 같은 점화식을 만족시킨다.
$$\displaystyle B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k $$
집합 $$\left\{1,~2, \cdots\cdots ,~n+1 \right\}$$을 분할한다고 하자. 이때 각각의 분할에서는 $$1$$을 원소로 갖는 집합이 있을 것이다. $$1$$을 원소로 갖는 집합의 원소의 개수가 $$k$$가 되도록 분할하는 경우의 수는 $$n$$개 중에서 $$1$$을 제외한 $$(k-1)$$개를 고르는 경우의 수 $$\dbinom n{k-1}$$에 나머지 $$n-(k-1)$$개의 원소를 분할하는 경우의 수 $$B_{n-k+1}$$를 곱한 값 $$\dbinom n{k-1} B_{n-k+1}$$임을 알 수 있다. $$k$$는 $$1$$부터 $$(n+1)$$까지의 값을 취할 수 있고 $$k$$가 다른 값을 취할 때 중복되는 경우는 없으므로 합의 법칙에 의하여
$$\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$$

3. 관련 문서


[1] '공집합을 분할'한다는 개념이 와닿지 않을 수 있으나, 대수적으로도 정의되는 제2종 스털링 수와의 관계에 따라 $$n=0$$일 때에도 정의가 된다. $$S \left( 0,~0 \right) = 1$$이기 때문.

분류