벨 수 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Set partitions 5; circles.svg|섬네일|right|5개의 원소의 [[집합의 분할]]. 총 52가지가 있으며, 따라서 <math>B_5=52</math>이다.]]
[[파일:Set_partitions_4;_list.svg|섬네일|right|4개의 원소의 [[집합의 분할]]. 총 15가지가 있으며, 따라서 <math>B_4=15</math>이다.]]
[[조합론]]에서 '''벨 수'''(Bell數, {{llang|en|Bell number}})는 주어진 크기의 집합의 분할의 수를 세는 [[정수열]]이다. [[12정도]]의 해 가운데 하나이며, 또한 [[푸아송 분포]]의 모멘트이다.

== 정의 ==
''n''번째 '''벨 수'''({{llang|en|Bell number}}) ''B''<sub>''n''</sub>은 n개의 원소들로 구성된 [[집합]]을 [[집합의 분할|분할]]하는 방법의 가지수이다. 이는 ''n''개의 원소들 사이의 [[동치 관계]]의 수로 생각할 수 있으며, 또 <math>n</math>행의 시에서 가능한 [[각운]] 패턴의 수로도 여길 수 있다.<ref name="Gardner"/>

[[제2종 스털링 수]] <math>\textstyle\{{n\atop k}\}</math>는 <math>n</math>개의 원소들로 구성된 집합을 <math>k</math>개의 조각으로 분할하는 방법의 수이다. 따라서 벨 수는 [[제2종 스털링 수]]의 합이다.
:<math>B_n=\sum_{k=0}^n\left\{{n\atop k}\right\}</math>

=== 투샤르 다항식 ===
'''투샤르 다항식'''({{llang|en|Touchard polynomial}}) 또는 [[벨 다항식]]({{llang|en|Bell polynomial}})은 다음과 같은 다항식열이다.
:<math>T_n(x)=\sum_{k=0}^n\left\{{n\atop k}\right\}x^k</math>
이는 [[음계산법]]을 써 다음과 같이 표기할 수 있다.<ref name="KRY">{{서적 인용
 |last          = Kung
 |first         = Joseph P. S.
 |이름2       = Gian-Carlo
 |성2          = Rota
 |저자링크2 = 잔카를로 로타
 |이름3       = Catherine H.
 |성3          = Yan
 |title         = Combinatorics: The Rota Way
 |url           = http://www.math.tamu.edu/~cyan/book.html
 |publisher     = Cambridge University Press
 |series        = Cambridge Mathematical Library
 |날짜        = 2009
 |isbn          = 978-0-521-88389-4
 |doi           = 10.1017/CBO9780511803895
 |언어        = en
 |확인날짜  = 2015-10-28
 |보존url     = https://web.archive.org/web/20160303222342/http://www.math.tamu.edu/~cyan/book.html
 |보존날짜  = 2016-03-03
 |url-status  = dead
}}</ref>{{rp|186–187}} [[하강 포흐하머 기호]]는 [[이항형 다항식열]]을 이루므로, 다음과 같은 선형 범함수를 정의하자.
:<math>L\colon\mathbb Q[x]\to\mathbb Q[x]</math>
:<math>L\colon x^n\mapsto x^{\underline n}</math>
여기서 <math>x^{\underline n}</math>은 [[하강 포흐하머 기호]]이다. 이 범함수의 역범함수
:<math>L\colon\mathbb Q[x]\to\mathbb Q[x]</math>
:<math>L\colon x^{\underline n}\mapsto x^n</math>
를 생각하면,
:<math>L(x^n)=T_n(x)</math>
가 된다.

벨 수는 투샤르 다항식의 <math>x=1</math>인 값이다.
:<math>B_n=T_n(1)=\sum_{k=0}^n\left\{{n\atop k}\right\}</math>
투샤르 다항식은 [[이항형 다항식열]]이다. 이에 대응하는 델타 작용소는 <math>D\mapsto \exp D-1</math>의 역함수인
:<math>\log\left(1+\frac{d}{dx}\right)</math>
이다.

== 표 ==
벨 수열의 값은 다음과 같다. (''B''<sub>0</sub> = ''B''<sub>1</sub> = 1부터 시작한다.) {{OEIS|A000110}}
: [[1]], 1, [[2]], [[5]], [[15]], [[52]], [[203]], [[877]], [[4140]], 21147, 115975, …

투샤르 다항식열의 값은 다음과 같다.
:<math>T_0(x)=1</math>
:<math>T_1(x)=x</math>
:<math>T_2(x)=x^2+x</math>
:<math>T_3(x)=x^3+3x^2+x</math>
:<math>T_4(x)=x^4+6x^3+7x^2+x</math>
:<math>T_5(x)=x^5+10x^4+25x^3+15x^2+x</math>
:<math>T_6(x)=x^6+15x^5+65x^4+90x^3+31x^2+x</math>

== 성질 ==
=== 점화식 ===
투샤르 다항식과 벨 수는 다음과 같은 [[점화식]]을 만족시킨다.
:<math>T_{n+1}(x)=x\sum_{k=0}^n\binom nk T_n(x)</math>
:<math>B_{n+1}=\sum_{k=0}^n \binom nkB_k</math>

이는 [[음계산법]]으로 표기하면 다음과 같다.<ref name="KRY"/>{{rp|187, Lemma 4.2.3}}
:<math>L^{-1}(x^{n+1})=xL^{-1}\left((x+1)^n\right)</math>

=== 도빈스키 공식 ===
다음 공식은 '''도빈스키 공식'''({{llang|en|Dobiński’s formula}})라고 불린다.<ref name="Dobinski"/>
:<math>B_n=\frac1e\sum_{k=0}^\infty \frac{k^n}{k!}</math>
이에 따라, <math>n</math>번째 벨 수는 [[기댓값]]이 1인 [[푸아송 분포]]
:<math>\Pr(x=k)=\frac1e\frac1{k!}</math>
의 <math>n</math>번째 [[모멘트 (수학)|모멘트]]이다.

이는 [[음계산법]]으로 다음과 같이 유도할 수 있다.<ref name="KRY"/>{{rp|188, 4.2.4}} 우선
:<math>\forall n\colon \exp x=\sum_{k=0}^\infty\frac{x^k}{k!}=\sum_{k=0}^\infty \frac{x^kk^{\underline n}}{k!}</math>
이다. 따라서,
:<math>\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}</math>
이므로,
:<math>\operatorname{eval}_{x\mapsto1}\circ L^{-1}=\frac1e\sum_{k=0}^\infty \frac1{k!}\operatorname{eval}_{x\mapsto k}</math>
이다. 즉,
:<math>B_n=\operatorname{eval}_{x\mapsto1}L^{-1}(x^n)=\frac1e\sum_{k=0}^\infty\frac1{k!}k^n</math>
가 된다.

=== 생성 함수 ===
투샤르 다항식 및 벨 수는 다음과 같은 [[생성 함수 (수학)|지수 생성 함수]]를 갖는다.
:<math>\sum_{n=0}^\infty T_n(x)\frac{t^n}{n!}=L^{-1}\exp(xt)=\exp(x(\exp(t)-1))</math>
:<math>\sum_{n=0}^\infty B_n\frac{t^n}{n!} =\operatorname{eval}_{x\mapsto1} L^{-1}\exp(xt)= \exp(\exp(t)-1)</math>
이는 [[음계산법]]을 사용하여 쉽게 유도할 수 있다.<ref name="KRY"/>{{rp|186, Theorem 4.2.2}}  [[하강 포흐하머 기호]]의 델타 작용소는 전방 [[유한 차분]]
:<math>\Delta f=f(x+1)-f(x)</math>
이며, 따라서
:<math>L\frac d{dx}=\Delta L</math>
이다. 즉,
:<math>\frac d{dx}L^{-1}=L^{-1}\Delta</math>
이다. 그런데
:<math>\Delta\exp(xt)=\left(\exp(t)-1\right)\exp(xt)</math>
이므로
:<math>\frac d{dx}L^{-1}\exp(xt)=\left(\exp(t)-1\right)L^{-1}\exp(xt)</math>
이다. 따라서
:<math>L^{-1}\exp(xt)=\exp\left(x\left(\exp(t)-1\right)\right)</math>
이다.

=== 적분 표현 ===
지수 생성 함수에 [[코시 적분 정리]]를 사용하여, 투샤르 다항식과 벨 수를 다음과 같이 [[선적분]]으로 나타낼 수 있다.
: <math> T_n(x) = \frac{n!}{2 \pi i} \oint_{\gamma} \frac{\exp(x(\exp(z)-1))}{z^{n+1}} \, dz</math>
: <math> B_n = T_n(1) = \frac{n!}{2 \pi i} \oint_{\gamma} \frac{\exp(\exp(z)-1)}{z^{n+1}} \, dz</math>
여기서 <math>\gamma</math>는 원점을 시계 반대 방향으로 한 번 도는 임의의 폐곡선이다.

== 역사 ==
[[파일:Set partitions 5; Genji symbols.svg|섬네일|52개의 겐지몬의 답안([[:ja:香の図]]) . 원래 겐지몬은 채색되어 있지 않으며, 색깔은 대응하는 [[집합의 분할]]을 구체적으로 보이기 위해 첨가하였다.]]
[[파일:Illustration Genji Monogatari Musée Saint-Remi 928 4.jpg|섬네일|right|19세기 《[[겐지모노가타리]]》 삽화. 왼쪽 상단에 6장 〈스에쓰무하나〉({{llang|ja|末摘花}})에 대응하는 겐지몬이 표시돼 있다.]]
벨 수는 중세 [[일본]] 수학에서 최초로 등장한다. 《[[겐지모노가타리]]》에서의 한 일화로부터 겐지코({{llang|ja|源氏香}})(c.f.[[:ja:香道]])라는 놀이가 등장했는데,<ref name="Gardner">{{저널 인용
 | last = Gardner | first = Martin
 | doi = 10.1038/scientificamerican0578-24
 | journal = Scientific American
 | pages = 24–30
 | title = The Bells: versatile numbers that can count partitions of a set, primes and even rhymes
 | volume = 238
 | year = 1978|언어=en}}</ref> 이 놀이에서는 5개의 향 가운데 어떤 것들이 같은 냄새의 향인지 구별하는 것이 목표이다. 가능한 해의 수는 벨 수에 따라 총 <math>B_5=52</math>가지다. 이 52가지의 벨 수는 겐지몬({{llang|ja|源氏紋}})이라는 문양으로 나타내어져, [[겐지모노가타리]]의 54개의 장의 각 표지에 표시되었다. (이 가운데 54장 〈유메 노 우키하시〉({{llang|ja|夢浮橋}})에는 벨 수와 관계없는 겐지몬이 붙어 있으며, 35장 〈와카나 노 게〉({{llang|ja|若菜下}}) 와 42장 〈니오노미야〉({{llang|ja|匂宮}})의 겐지몬은 모양이 다르지만 같은 [[집합의 분할]]에 대응한다.)

{| 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년에 폴란드의 구스타브 도빈스키({{llang|pl|Gustaw Dobiński}})가 오늘날 도빈스키 공식이라고 불리는, 벨 수에 대한 공식을 발표하였다.<ref name="Dobinski">{{저널 인용|first=G.|last=Dobiński|title=Summirung der Reihe <math>\textstyle\sum\frac{n^m}{n!}</math> für ''m''&nbsp;=&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;…|저널=Archiv der Mathematik und Physik mit besonderer Rücksicht auf die Bedürfnisse der Lehrer an höheren Unterrichtsanstalten|volume=61|날짜=1877|pages=333–336|url=http://www.archive.org/stream/archivdermathem88unkngoog#page/n346|jfm= 09.0178.04|언어=de}}</ref> 벨 삼각형은 [[찰스 샌더스 퍼스]]가 1880년에,<ref>{{저널 인용
 | last = Peirce | first = C. S. | authorlink = 찰스 샌더스 퍼스
 | issue = 1
 | journal = American Journal of Mathematics
 | jstor = 2369442
 | pages = 15–57
 | title = On the algebra of logic
 | volume = 3
 | 날짜 = 1880|jfm=12.0041.01|언어=en}}</ref> 알렉산더 에잇컨({{llang|en|Alexander C. Aitken}})이 1933년에<ref>{{저널 인용
 | 성 = Aitken | 이름 = A. C.
 | doi = 10.1017/S1757748900002334
 | 저널 = Edinburgh Mathematical Notes
 | 쪽 = 18–23
 | title = A problem in combinations
 | 권 = 28
 | 날짜 = 1933
 | jfm=59.0937.01|zbl=0007.38907
 | 언어=en}}</ref> 거론하였다.

[[스리니바사 라마누잔]]은 노트 2권<ref>{{서적 인용|이름=Srinivasa|성=Ramanujan|저자링크=스리니바사 라마누잔|제목=Notebooks Vol. 2|출판사=Tata Institute of Fundamental Research|위치=[[뭄바이]]|날짜=1957|언어=en}}</ref> 3장에서 투샤르 다항식과 벨 수에 대하여 연구하였으나, 출판하지 않았다.<ref>{{저널 인용
 | last = Berndt | first = Bruce C.
 | journal = Asia Pacific Mathematics Newsletter
 | pages = 8–13
 | title = Ramanujan reaches his hand from his grave to snatch your theorems from you
 | url = http://www.asiapacific-mathnews.com/01/0102/0008_0013.pdf
 | 권 = 1 | 호=2
 | 날짜 = 2011-04
 | 언어=en}}</ref>

[[에릭 템플 벨]]({{llang|en|Eric Temple Bell}})은 이 수들에 대하여 1934년부터 다루기 시작하였다.<ref>{{저널 인용|first=E. T.|last=Bell|title= Exponential polynomials|journal=Annals of Mathematics|volume=35|year=1934|pages=258–277|jstor=1968431|jfm=60.0295.01|zbl=0009.21202|언어=en}}</ref> 벨은 원래 이 수들을 "지수적 수"({{llang|en|exponential number}})라고 불렀으나, 이후 벨을 기려 "벨 수"라고 불리게 되었다. 자크 투샤르({{llang|fr|Jacques Touchard}})는 투샤르 다항식을 1939년에 도입하였다.<ref>{{저널 인용 | last1=Touchard | first1=Jacques | title=Sur les cycles des substitutions | doi=10.1007/BF02547349 | mr=1555449 | year=1939 | journal=Acta Mathematica | issn=0001-5962 | volume=70 | issue=1 | pages=243–297}}</ref>

== 같이 보기 ==
* [[집합의 분할]]
* [[스털링 수]]
* [[12정도]]
* [[포흐하머 기호]]
* [[음계산법]]
* [[베르누이 수]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=BellNumber|title=Bell number}}
* {{매스월드|id=BellTriangle|title=Bell triangle}}
* {{매스월드|id=BellPolynomial|title=Bell polynomial}}
* {{매스월드|id=ComplementaryBellNumber|title=Complementary Bell number}}
* {{매스월드|id=DobinskisFormula|title=Dobiński's Formula}}

[[분류:조합론]]
[[분류:정수열]]