위키득계정 ↗
과학

벨 수

벨 수과학
영어
Bell number
표기
Bₙ
세는 대상
n원소 집합의 모든 분할
스털링 수와의 관계
Bₙ=Σ S(n,k), 0≤k≤n
벨 수 Bₙ은 서로 다른 n개 원소로 이루어진 집합을 비어 있지 않은 부분집합들로 분할하는 모든 방법의 수다. 블록의 개수는 고정하지 않으며 블록 사이의 순서는 구분하지 않는다. B₀=1에서 시작해 1, 1, 2, 5, 15, 52로 이어진다.

블록 수를 정하지 않는 분할

제2종 스털링 수는 블록 개수를 정한 상태에서 분할을 센다. 벨 수는 블록이 몇 개가 되는지 제한하지 않고 가능한 분할을 모두 센다. 따라서 원소 수 n을 고정하고 S(n,0)부터 S(n,n)까지 더하면 Bₙ이 된다.

세 원소에서 다섯 가지

{a,b,c}의 분할은 세 원소가 한 블록에 있는 경우 한 가지, 두 블록인 경우 세 가지, 모두 따로 놓이는 경우 한 가지다. 따라서 B₃=1+3+1=5다. 두 블록의 순서를 바꿔 다시 세지 않으며 블록 내부에서도 원소의 나열 순서를 구분하지 않는다.

한 원소가 속한 블록

n≥1에서 특정 원소 하나를 고르면 그 원소와 같은 블록에 들어갈 나머지 원소들을 선택할 수 있다. 같은 블록에 넣지 않은 k개 원소는 다시 Bₖ가지로 분할한다. k를 0부터 n−1까지 바꾸어 더하면 Bₙ=Σ binom(n−1,k)Bₖ라는 점화식을 얻는다.

다른 세기와의 차이

집합의 부분집합을 하나 선택하는 문제는 벨 수가 세는 분할 문제와 다르다. 블록들에 순서를 부여하는 경우에도 별도의 수열이 된다. 또한 Bₙ은 베르누이 수 표기에도 쓰이므로 기호만으로 판단하지 말고 어떤 대상을 세는지 확인해야 한다.

관련 문서

제2종 스털링 수 / 집합의 분할 / 부분집합 / 이항계수 / 점화식 / 카탈랑 수