벨 수

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

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

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

정의

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

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

$B_n=\sum _{k=0}^n\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$

투샤르 다항식

투샤르 다항식(틀:Llang) 또는 벨 다항식(틀:Llang)은 다음과 같은 다항식열이다.

$T_n(x)=\sum _{k=0}^n\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}{x}^k$

이는 음계산법을 써 다음과 같이 표기할 수 있다.틀:Rp 하강 포흐하머 기호는 이항형 다항식열을 이루므로, 다음과 같은 선형 범함수를 정의하자.

$L:\mathbb{Q}[x]\to \mathbb{Q}[x]$

$L:x^n\mapsto x^{\underset{\_}{n}}$

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

$L:\mathbb{Q}[x]\to \mathbb{Q}[x]$

$L:x^{\underset{\_}{n}}\mapsto x^n$

를 생각하면,

$L(x^n)=T_n(x)$

가 된다.

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

$B_n=T_n(1)=\sum _{k=0}^n\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$

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

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

이다.

표

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

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(\genfrac{}{}{0ex}{}{n}{k})T_n(x)$

$B_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})B_k$

이는 음계산법으로 표기하면 다음과 같다.틀:Rp

$L^{-1}(x^{n+1})=x{L}^{-1}((x+1{)}^n)$

도빈스키 공식

다음 공식은 도빈스키 공식(틀:Llang)라고 불린다.

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

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

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

의 $n$번째 모멘트이다.

이는 음계산법으로 다음과 같이 유도할 수 있다.틀:Rp 우선

$\mathrm{\forall }n:\exp x=\sum _{k=0}^{\mathrm{\infty }}\frac{x^k}{k!}=\sum _{k=0}^{\mathrm{\infty }}\frac{x^k{k}^{\underset{\_}{n}}}{k!}$

이다. 따라서,

${\mathrm{eval}}_{x\mapsto 1}\circ L^{-1}:x^{\underset{\_}{n}}\mapsto 1=\frac{1}{e}\sum _{k=0}^{\mathrm{\infty }}\frac{1}{k!}{\mathrm{eval}}_{x\mapsto k}{x}^{\underset{\_}{n}}$

이므로,

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

이다. 즉,

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

가 된다.

생성 함수

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

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

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

이는 음계산법을 사용하여 쉽게 유도할 수 있다.틀:Rp 하강 포흐하머 기호의 델타 작용소는 전방 유한 차분

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

이며, 따라서

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

이다. 즉,

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

이다. 그런데

$\mathrm{\Delta }\exp (xt)=(\exp (t)-1)\exp (xt)$

이므로

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

이다. 따라서

$L^{-1}\exp (xt)=\exp \left(x(\exp (t)-1)\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세기 《겐지모노가타리》 삽화. 왼쪽 상단에 6장 〈스에쓰무하나〉(틀:Llang)에 대응하는 겐지몬이 표시돼 있다.

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

번호	제목	집합의 분할
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년에 폴란드의 구스타브 도빈스키(틀:Llang)가 오늘날 도빈스키 공식이라고 불리는, 벨 수에 대한 공식을 발표하였다. 벨 삼각형은 찰스 샌더스 퍼스가 1880년에, 알렉산더 에잇컨(틀:Llang)이 1933년에 거론하였다.

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

에릭 템플 벨(틀:Llang)은 이 수들에 대하여 1934년부터 다루기 시작하였다. 벨은 원래 이 수들을 "지수적 수"(틀:Llang)라고 불렀으나, 이후 벨을 기려 "벨 수"라고 불리게 되었다. 자크 투샤르(틀:Llang)는 투샤르 다항식을 1939년에 도입하였다.

같이 보기

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

외부 링크

• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드