벨 수(Bell Number)는 n개의 원소를 가진 집합을 공집합이 아닌(최소 한 개 이상의 원소를 포함하는) 부분 집합들로 나누는 방법의 총 가짓수를 나타내는 수입니다.
이 글에서는 n개의 원소로 이루어진 집합이 주어졌을 때, 이를 빈 집합이 아닌 부분 집합들로 분할하는 모든 경우의 수를 구하는 프로그램을 만들어 보겠습니다.
예시
입력 : 3 출력 : 5
설명 − 세 원소로 이루어진 집합 {1, 2, 3}을 생각해 봅시다.
가능한 모든 분할은 다음과 같습니다.
{{1}, {2}, {3}} ; {{1}, {2, 3}} ; {{1, 2}, {3}} ; {{2}, {1, 3}} ; {{1, 2, 3}}
총 5가지이므로 출력은 5가 됩니다.
벨 수의 정의와 점화식
벨 수 bell(n)은 k가 0부터 n까지의 모든 값에 대해 S(n,k)의 합으로 정의됩니다. 여기서 S(n,k)는 n개의 원소를 정확히 k개의 부분 집합으로 나누는 방법의 수입니다.
수식은 다음과 같습니다.
$$bell(n)=\sum_{k=0}^n S(n,k)$$
S(n,k) 함수는 다음과 같이 재귀적으로(점화식 형태로) 정의할 수 있습니다.
s(n+1, k) = k × s(n, k) + s(n, k-1)
동작 원리
(n+1)번째 원소를 기존 k개의 분할 구조에 추가할 때는 두 가지 경우가 존재합니다.
새로운 독립적인 분할(단독 부분 집합)로 추가되는 경우 → s(n, k-1)에 해당합니다.
기존 k개의 분할 중 어느 하나에 포함되는 경우 → k × s(n, k)에 해당합니다.
처음 몇 개의 벨 수는 다음과 같습니다.
1, 1, 2, 5, 15, 52, 205
벨 수를 구하는 방법
단순한 방법 − k = 1부터 n까지 s(n, k)를 하나씩 차례대로 계산한 뒤, 모든 값을 더하여 합을 구합니다.
벨 삼각형(Bell Triangle) 활용 − 아래와 같은 벨 삼각형을 이용하면 효율적으로 벨 수를 계산할 수 있습니다.
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52
벨 삼각형에서 각 행의 첫 번째 값이 바로 그 인덱스에 해당하는 벨 수입니다. 즉 bell(0)=1, bell(1)=1, bell(2)=2, bell(3)=5, bell(4)=15, bell(5)=52 순으로 나타납니다. 삼각형의 규칙은 각 행의 첫 값이 바로 위 행의 마지막 값이며, 이후의 값은 왼쪽 값과 바로 위 왼쪽 대각선 값을 더한 것입니다.
C++ 구현 예시
#include<iostream>
using namespace std;
int bellNumber(int n) {
int bell[n+1][n+1];
bell[0][0] = 1;
for (int i=1; i<=n; i++) {
bell[i][0] = bell[i-1][i-1];
for (int j=1; j<=i; j++)
bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
}
return bell[n][0];
}
int main() {
for (int n=0; n<=5; n++)
cout<<"Bell Number "<<n<<" is "<< bellNumber(n)<<endl;
return 0;
}실행 결과
Bell Number 0 is 1 Bell Number 1 is 1 Bell Number 2 is 2 Bell Number 3 is 5 Bell Number 4 is 15 Bell Number 5 is 52