벨 수

조합론에서 벨 수(Bell數, 영어: Bell number)는 주어진 크기의 집합의 분할의 수를 세는 정수열이다. 12정도의 해 가운데 하나이며, 또한 푸아송 분포의 모멘트이다.

5개의 원소의 집합의 분할. 총 52가지가 있으며, 따라서 ${\displaystyle B_{5}=52}$이다.

4개의 원소의 집합의 분할. 총 15가지가 있으며, 따라서 ${\displaystyle B_{4}=15}$이다.

정의

n번째 벨 수(영어: Bell number) B_n은 n개의 원소들로 구성된 집합을 분할하는 방법의 가지수이다. 이는 n개의 원소들 사이의 동치 관계의 수로 생각할 수 있으며, 또 ${\displaystyle n}$행의 시에서 가능한 각운 패턴의 수로도 여길 수 있다.^[1]

제2종 스털링 수 ${\displaystyle \textstyle \{{n \atop k}\}}$는 ${\displaystyle n}$개의 원소들로 구성된 집합을 ${\displaystyle k}$개의 조각으로 분할하는 방법의 수이다. 따라서 벨 수는 제2종 스털링 수의 합이다.

${\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}}$

투샤르 다항식

투샤르 다항식(영어: Touchard polynomial) 또는 벨 다항식(영어: Bell polynomial)은 다음과 같은 다항식열이다.

${\displaystyle T_{n}(x)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}x^{k}}$

이는 음계산법을 써 다음과 같이 표기할 수 있다.^{[2]:186–187} 하강 포흐하머 기호는 이항형 다항식열을 이루므로, 다음과 같은 선형 범함수를 정의하자.

${\displaystyle L\colon \mathbb {Q} [x]\to \mathbb {Q} [x]}$

${\displaystyle L\colon x^{n}\mapsto x^{\underline {n}}}$

여기서 ${\displaystyle x^{\underline {n}}}$은 하강 포흐하머 기호이다. 이 범함수의 역범함수

${\displaystyle L\colon \mathbb {Q} [x]\to \mathbb {Q} [x]}$

${\displaystyle L\colon x^{\underline {n}}\mapsto x^{n}}$

를 생각하면,

${\displaystyle L(x^{n})=T_{n}(x)}$

가 된다.

벨 수는 투샤르 다항식의 ${\displaystyle x=1}$인 값이다.

${\displaystyle B_{n}=T_{n}(1)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}}$

투샤르 다항식은 이항형 다항식열이다. 이에 대응하는 델타 작용소는 ${\displaystyle D\mapsto \exp D-1}$의 역함수인

${\displaystyle \log \left(1+{\frac {d}{dx}}\right)}$

이다.

표

벨 수열의 값은 다음과 같다. (B₀ = B₁ = 1부터 시작한다.) (OEIS의 수열 A000110)

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …

투샤르 다항식열의 값은 다음과 같다.

${\displaystyle T_{0}(x)=1}$

${\displaystyle T_{1}(x)=x}$

${\displaystyle T_{2}(x)=x^{2}+x}$

${\displaystyle T_{3}(x)=x^{3}+3x^{2}+x}$

${\displaystyle T_{4}(x)=x^{4}+6x^{3}+7x^{2}+x}$

${\displaystyle T_{5}(x)=x^{5}+10x^{4}+25x^{3}+15x^{2}+x}$

${\displaystyle T_{6}(x)=x^{6}+15x^{5}+65x^{4}+90x^{3}+31x^{2}+x}$

성질

점화식

투샤르 다항식과 벨 수는 다음과 같은 점화식을 만족시킨다.

${\displaystyle T_{n+1}(x)=x\sum _{k=0}^{n}{\binom {n}{k}}T_{n}(x)}$

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}}$

이는 음계산법으로 표기하면 다음과 같다.^{[2]:187, Lemma 4.2.3}

${\displaystyle L^{-1}(x^{n+1})=xL^{-1}\left((x+1)^{n}\right)}$

도빈스키 공식

다음 공식은 도빈스키 공식(영어: Dobiński’s formula)라고 불린다.^[3]

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}}$

이에 따라, ${\displaystyle n}$번째 벨 수는 기댓값이 1인 푸아송 분포

${\displaystyle \Pr(x=k)={\frac {1}{e}}{\frac {1}{k!}}}$

의 ${\displaystyle n}$번째 모멘트이다.

이는 음계산법으로 다음과 같이 유도할 수 있다.^{[2]:188, 4.2.4} 우선

${\displaystyle \forall n\colon \exp x=\sum _{k=0}^{\infty }{\frac {x^{k}}{k!}}=\sum _{k=0}^{\infty }{\frac {x^{k}k^{\underline {n}}}{k!}}}$

이다. 따라서,

${\displaystyle \operatorname {eval} _{x\mapsto 1}\circ L^{-1}\colon x^{\underline {n}}\mapsto 1={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\operatorname {eval} _{x\mapsto k}x^{\underline {n}}}$

이므로,

${\displaystyle \operatorname {eval} _{x\mapsto 1}\circ L^{-1}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\operatorname {eval} _{x\mapsto k}}$

이다. 즉,

${\displaystyle B_{n}=\operatorname {eval} _{x\mapsto 1}L^{-1}(x^{n})={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}k^{n}}$

가 된다.

생성 함수

투샤르 다항식 및 벨 수는 다음과 같은 지수 생성 함수를 갖는다.

${\displaystyle \sum _{n=0}^{\infty }T_{n}(x){\frac {t^{n}}{n!}}=L^{-1}\exp(xt)=\exp(x(\exp(t)-1))}$

${\displaystyle \sum _{n=0}^{\infty }B_{n}{\frac {t^{n}}{n!}}=\operatorname {eval} _{x\mapsto 1}L^{-1}\exp(xt)=\exp(\exp(t)-1)}$

이는 음계산법을 사용하여 쉽게 유도할 수 있다.^{[2]:186, Theorem 4.2.2} 하강 포흐하머 기호의 델타 작용소는 전방 유한 차분

${\displaystyle \Delta f=f(x+1)-f(x)}$

이며, 따라서

${\displaystyle L{\frac {d}{dx}}=\Delta L}$

이다. 즉,

${\displaystyle {\frac {d}{dx}}L^{-1}=L^{-1}\Delta }$

이다. 그런데

${\displaystyle \Delta \exp(xt)=\left(\exp(t)-1\right)\exp(xt)}$

이므로

${\displaystyle {\frac {d}{dx}}L^{-1}\exp(xt)=\left(\exp(t)-1\right)L^{-1}\exp(xt)}$

이다. 따라서

${\displaystyle L^{-1}\exp(xt)=\exp \left(x\left(\exp(t)-1\right)\right)}$

이다.

적분 표현

지수 생성 함수에 코시 적분 정리를 사용하여, 투샤르 다항식과 벨 수를 다음과 같이 선적분으로 나타낼 수 있다.

${\displaystyle T_{n}(x)={\frac {n!}{2\pi i}}\oint _{\gamma }{\frac {\exp(x(\exp(z)-1))}{z^{n+1}}}\,dz}$

${\displaystyle B_{n}=T_{n}(1)={\frac {n!}{2\pi i}}\oint _{\gamma }{\frac {\exp(\exp(z)-1)}{z^{n+1}}}\,dz}$

여기서 ${\displaystyle \gamma }$는 원점을 시계 반대 방향으로 한 번 도는 임의의 폐곡선이다.

역사

52개의 겐지몬의 답안(ja:香の図) . 원래 겐지몬은 채색되어 있지 않으며, 색깔은 대응하는 집합의 분할을 구체적으로 보이기 위해 첨가하였다.

19세기 《겐지모노가타리》 삽화. 왼쪽 상단에 6장 〈스에쓰무하나〉(일본어: 末摘花)에 대응하는 겐지몬이 표시돼 있다.

벨 수는 중세 일본 수학에서 최초로 등장한다. 《겐지모노가타리》에서의 한 일화로부터 겐지코(일본어: 源氏香)(c.f.ja:香道)라는 놀이가 등장했는데,^[1] 이 놀이에서는 5개의 향 가운데 어떤 것들이 같은 냄새의 향인지 구별하는 것이 목표이다. 가능한 해의 수는 벨 수에 따라 총 ${\displaystyle B_{5}=52}$가지다. 이 52가지의 벨 수는 겐지몬(일본어: 源氏紋)이라는 문양으로 나타내어져, 겐지모노가타리의 54개의 장의 각 표지에 표시되었다. (이 가운데 54장 〈유메 노 우키하시〉(일본어: 夢浮橋)에는 벨 수와 관계없는 겐지몬이 붙어 있으며, 35장 〈와카나 노 게〉(일본어: 若菜下) 와 42장 〈니오노미야〉(일본어: 匂宮)의 겐지몬은 모양이 다르지만 같은 집합의 분할에 대응한다.)

번호	제목	집합의 분할
1	기리쓰보	13, 2, 45
2	하하키기	1, 2, 3, 4, 5
3	우쓰세미	1, 2, 3, 45
4	유가오	1, 2, 34, 5
5	와카무라사키	1, 23, 45
6	스에쓰무하나	1234, 5
7	모미지 노 가	1, 235, 4
8	하나 노 엔	1, 2, 35, 4
9	아오이	12, 3, 4, 5
10	사사키	123, 45
11	하나 치루 사토	1, 24, 35
12	스마	134, 25
13	아카시	1, 23, 4, 5
14	미오쓰쿠시	1, 245, 3
15	요모규	123, 4, 5
16	세키야	1, 234, 5
17	에아와세	13, 25, 4
18	마쓰카제	12, 34, 5
19	우스구모	1, 2345
20	아사가오	134, 2, 5
21	오토메	13, 2, 4, 5
22	다마카즈라	12, 345
23	하쓰네	13, 24, 5
24	고초	14, 235
25	호타루	124, 3, 5
26	도코나쓰	1, 2, 345
27	가가리비	1, 24, 3, 5
28	노와키	12, 3, 45
29	미유키	13, 245
30	후지바카마	14, 2, 3, 5
31	마키바시라	15, 24, 3
32	우메가에	1235, 4
33	후지 노 우라바	1, 25, 34
34	와카나 노 조	125, 34
35	와카나 노 게	124, 35 (분할은 42와 같지만, 겐지몬이 다름)
36	가시와기	135, 2, 4
37	요코부에	145, 2, 3
38	스즈무시	15, 2, 34
39	유기리	14, 2, 35
40	미노리	14, 25, 3
41	마보로시	15, 2, 3, 4
42	니오노미야	124, 35 (분할은 35와 같지만, 겐지몬이 다름)
43	고바이	1, 25, 3, 4
44	다케가와	15, 234
45	하시히메	1345, 2
46	시가모토	14, 23, 5
47	아게마키	145, 23
48	사와라비	12, 35, 4
49	야도리기	1245, 3
50	아즈마야	125, 3, 4
51	우키후네	15, 23, 4
52	가게로	135, 24
53	데나라이	12345
54	유메 노 우키하시	(물결 모양, 집합 분할과 관계없음)

1877년에 폴란드의 구스타브 도빈스키(폴란드어: Gustaw Dobiński)가 오늘날 도빈스키 공식이라고 불리는, 벨 수에 대한 공식을 발표하였다.^[3] 벨 삼각형은 찰스 샌더스 퍼스가 1880년에,^[4] 알렉산더 에잇컨(영어: Alexander C. Aitken)이 1933년에^[5] 거론하였다.

스리니바사 라마누잔은 노트 2권^[6] 3장에서 투샤르 다항식과 벨 수에 대하여 연구하였으나, 출판하지 않았다.^[7]

에릭 템플 벨(영어: Eric Temple Bell)은 이 수들에 대하여 1934년부터 다루기 시작하였다.^[8] 벨은 원래 이 수들을 "지수적 수"(영어: exponential number)라고 불렀으나, 이후 벨을 기려 "벨 수"라고 불리게 되었다. 자크 투샤르(프랑스어: Jacques Touchard)는 투샤르 다항식을 1939년에 도입하였다.^[9]

같이 보기

• 집합의 분할
• 스털링 수
• 12정도
• 포흐하머 기호
• 음계산법
• 베르누이 수