벨 수

5개의 원소의 집합의 분할. 총 52가지가 있으며, 따라서 B_5=52이다. 4개의 원소의 집합의 분할. 총 15가지가 있으며, 따라서 B_4=15이다. 조합론에서 **벨 수**(Bell數, Bell number)는 주어진 크기의 집합의 분할의 수를 세는 정수열이다. 12정도의 해 가운데 하나이며, 또한 푸아송 분포의 모멘트이다.
# 정의
*n*번째 **벨 수**(Bell number) *B**n*은 n개의 원소들로 구성된 집합을 분할하는 방법의 가지수이다. 이는 *n*개의 원소들 사이의 동치 관계의 수로 생각할 수 있으며, 또 n행의 시에서 가능한 각운 패턴의 수로도 여길 수 있다. 제2종 스털링 수 \textstyle\\n\atop k}\\}는 n개의 원소들로 구성된 집합을 k개의 조각으로 분할하는 방법의 수이다. 따라서 벨 수는 제2종 스털링 수의 합이다. :B_n=\sum_{k=0}^n\left\\n\atop k}\right\\}
## 투샤르 다항식
**투샤르 다항식**(Touchard polynomial) 또는 벨 다항식(Bell polynomial)은 다음과 같은 다항식열이다. :T_n(x)=\sum_{k=0}^n\left\\n\atop k}\right\\}x^k 이는 음계산법을 써 다음과 같이 표기할 수 있다.url-status = dead186–187 하강 포흐하머 기호는 이항형 다항식열을 이루므로, 다음과 같은 선형 범함수를 정의하자. :L\colon\mathbb Q[x]\to\mathbb Q[x] :L\colon x^n\mapsto x^{\underline n} 여기서 x^{\underline n}은 하강 포흐하머 기호이다. 이 범함수의 역범함수 :L\colon\mathbb Q[x]\to\mathbb Q[x] :L\colon x^{\underline n}\mapsto x^n 를 생각하면, :L(x^n)=T_n(x) 가 된다. 벨 수는 투샤르 다항식의 x=1인 값이다. :B_n=T_n(1)=\sum_{k=0}^n\left\\n\atop k}\right\\} 투샤르 다항식은 이항형 다항식열이다. 이에 대응하는 델타 작용소는 D\mapsto \exp D-1의 역함수인 :\log\left(1+\frac{d}{dx}\right) 이다.
# 표
벨 수열의 값은 다음과 같다. (*B*0 = *B*1 = 1부터 시작한다.) A000110 : 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, … 투샤르 다항식열의 값은 다음과 같다. :T_0(x)=1 :T_1(x)=x :T_2(x)=x^2+x :T_3(x)=x^3+3x^2+x :T_4(x)=x^4+6x^3+7x^2+x :T_5(x)=x^5+10x^4+25x^3+15x^2+x :T_6(x)=x^6+15x^5+65x^4+90x^3+31x^2+x
# 성질

## 점화식
투샤르 다항식과 벨 수는 다음과 같은 점화식을 만족시킨다. :T_{n+1}(x)=x\sum_{k=0}^n\binom nk T_n(x) :B_{n+1}=\sum_{k=0}^n \binom nkB_k 이는 음계산법으로 표기하면 다음과 같다.187, Lemma 4.2.3 :L^{-1}(x^{n+1})=xL^{-1}\left((x+1)^n\right)
## 도빈스키 공식
다음 공식은 **도빈스키 공식**(Dobiński’s formula)라고 불린다. :B_n=\frac1e\sum_{k=0}^\infty \frac{k^n}{k!} 이에 따라, n번째 벨 수는 기댓값이 1인 푸아송 분포 :\Pr(x=k)=\frac1e\frac1{k!} 의 n번째 모멘트이다. 이는 음계산법으로 다음과 같이 유도할 수 있다.188, 4.2.4 우선 :\forall n\colon \exp x=\sum_{k=0}^\infty\frac{x^k}{k!}=\sum_{k=0}^\infty \frac{x^kk^{\underline n{k!} 이다. 따라서, :\operatorname{eval}_{x\mapsto1}\circ L^{-1}\colon x^{\underline n}\mapsto 1=\frac1e\sum_{k=0}^\infty \frac1{k!}\operatorname{eval}_{x\mapsto k}x^{\underline n} 이므로, :\operatorname{eval}_{x\mapsto1}\circ L^{-1}=\frac1e\sum_{k=0}^\infty \frac1{k!}\operatorname{eval}_{x\mapsto k} 이다. 즉, :B_n=\operatorname{eval}_{x\mapsto1}L^{-1}(x^n)=\frac1e\sum_{k=0}^\infty\frac1{k!}k^n 가 된다.
## 생성 함수
투샤르 다항식 및 벨 수는 다음과 같은 지수 생성 함수를 갖는다. :\sum_{n=0}^\infty T_n(x)\frac{t^n}{n!}=L^{-1}\exp(xt)=\exp(x(\exp(t)-1)) :\sum_{n=0}^\infty B_n\frac{t^n}{n!} =\operatorname{eval}_{x\mapsto1} L^{-1}\exp(xt)= \exp(\exp(t)-1) 이는 음계산법을 사용하여 쉽게 유도할 수 있다.186, Theorem 4.2.2 하강 포흐하머 기호의 델타 작용소는 전방 유한 차분 :\Delta f=f(x+1)-f(x) 이며, 따라서 :L\frac d{dx}=\Delta L 이다. 즉, :\frac d{dx}L^{-1}=L^{-1}\Delta 이다. 그런데 :\Delta\exp(xt)=\left(\exp(t)-1\right)\exp(xt) 이므로 :\frac d{dx}L^{-1}\exp(xt)=\left(\exp(t)-1\right)L^{-1}\exp(xt) 이다. 따라서 :L^{-1}\exp(xt)=\exp\left(x\left(\exp(t)-1\right)\right) 이다.
## 적분 표현
지수 생성 함수에 코시 적분 정리를 사용하여, 투샤르 다항식과 벨 수를 다음과 같이 선적분으로 나타낼 수 있다. : T_n(x) = \frac{n!}{2 \pi i} \oint_{\gamma} \frac{\exp(x(\exp(z)-1))}{z^{n+1 \, dz : B_n = T_n(1) = \frac{n!}{2 \pi i} \oint_{\gamma} \frac{\exp(\exp(z)-1)}{z^{n+1 \, dz 여기서 \gamma는 원점을 시계 반대 방향으로 한 번 도는 임의의 폐곡선이다.
# 역사
52개의 겐지몬의 답안(:ja:香の図) . 원래 겐지몬은 채색되어 있지 않으며, 색깔은 대응하는 [[집합의 분할을 구체적으로 보이기 위해 첨가하였다.]] 19세기 《末摘花)에 대응하는 겐지몬이 표시돼 있다. 벨 수는 중세 일본 수학에서 최초로 등장한다. 《겐지모노가타리》에서의 한 일화로부터 겐지코(源氏香)(c.f.:ja:香道)라는 놀이가 등장했는데,언어=en 이 놀이에서는 5개의 향 가운데 어떤 것들이 같은 냄새의 향인지 구별하는 것이 목표이다. 가능한 해의 수는 벨 수에 따라 총 B_5=52가지다. 이 52가지의 벨 수는 겐지몬(源氏紋)이라는 문양으로 나타내어져, 겐지모노가타리의 54개의 장의 각 표지에 표시되었다. (이 가운데 54장 〈유메 노 우키하시〉(夢浮橋)에는 벨 수와 관계없는 겐지몬이 붙어 있으며, 35장 〈와카나 노 게〉(若菜下) 와 42장 〈니오노미야〉(匂宮)의 겐지몬은 모양이 다르지만 같은 집합의 분할에 대응한다.) {| class="wikitable sortable" ! 번호 || 제목 || 집합의 분할 |- | 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)가 오늘날 도빈스키 공식이라고 불리는, 벨 수에 대한 공식을 발표하였다.언어=de 벨 삼각형은 찰스 샌더스 퍼스가 1880년에,언어=en 알렉산더 에잇컨(Alexander C. Aitken)이 1933년에언어=en 거론하였다. 스리니바사 라마누잔은 노트 2권언어=en 3장에서 투샤르 다항식과 벨 수에 대하여 연구하였으나, 출판하지 않았다.언어=en 에릭 템플 벨(Eric Temple Bell)은 이 수들에 대하여 1934년부터 다루기 시작하였다.언어=en 벨은 원래 이 수들을 "지수적 수"(exponential number)라고 불렀으나, 이후 벨을 기려 "벨 수"라고 불리게 되었다. 자크 투샤르(Jacques Touchard)는 투샤르 다항식을 1939년에 도입하였다.pages=243–297