벨 수

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

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

정의편집

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

제2종 스털링 수   개의 원소들로 구성된 집합을  개의 조각으로 분할하는 방법의 수이다. 따라서 벨 수는 제2종 스털링 수의 합이다.

 

투샤르 다항식편집

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

 

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

 
 

여기서  하강 포흐하머 기호이다. 이 범함수의 역범함수

 
 

를 생각하면,

 

가 된다.

벨 수는 투샤르 다항식의  인 값이다.

 

투샤르 다항식은 이항형 다항식열이다. 이에 대응하는 델타 작용소는  의 역함수인

 

이다.

편집

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

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

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

 
 
 
 
 
 
 

성질편집

점화식편집

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

 
 

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

 

도빈스키 공식편집

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

 

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

 

 번째 모멘트이다.

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

 

이다. 따라서,

 

이므로,

 

이다. 즉,

 

가 된다.

생성 함수편집

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

 
 

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

 

이며, 따라서

 

이다. 즉,

 

이다. 그런데

 

이므로

 

이다. 따라서

 

이다.

적분 표현편집

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

 
 

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

역사편집

 
52개의 겐지몬. 원래 겐지몬은 채색되어 있지 않으며, 색깔은 대응하는 집합의 분할을 구체적으로 보이기 위해 첨가하였다.
 
19세기 《겐지 이야기》 삽화. 왼쪽 상단에 6장 〈스에쓰무하나〉(일본어: 末摘花)에 대응하는 겐지몬이 표시돼 있다.

벨 수는 중세 일본 수학에서 최초로 등장한다. 《겐지 이야기》에서의 한 일화로부터 겐지코(일본어: 源氏香)라는 놀이가 등장했는데,[1] 이 놀이에서는 5개의 향 가운데 어떤 것들이 같은 냄새의 향인지 구별하는 것이 목표이다. 가능한 해의 수는 벨 수에 따라 총  가지다. 이 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]

같이 보기편집

참고 문헌편집

  1. Gardner, Martin (1978). “The Bells: versatile numbers that can count partitions of a set, primes and even rhymes”. 《Scientific American》 (영어) 238: 24–30. doi:10.1038/scientificamerican0578-24. 
  2. Kung, Joseph P. S.; Rota, Gian-Carlo; Yan, Catherine H. (2009). 《Combinatorics: The Rota Way》. Cambridge Mathematical Library (영어). Cambridge University Press. doi:10.1017/CBO9780511803895. ISBN 978-0-521-88389-4. 2016년 3월 3일에 원본 문서에서 보존된 문서. 2015년 10월 28일에 확인함. 
  3. Dobiński, G. (1877). “Summirung der Reihe   für m = 1, 2, 3, 4, 5, …”. 《Archiv der Mathematik und Physik mit besonderer Rücksicht auf die Bedürfnisse der Lehrer an höheren Unterrichtsanstalten》 (독일어) 61: 333–336. JFM 09.0178.04.  |title=에 지움 문자가 있음(위치 21) (도움말)
  4. Peirce, C. S. (1880). “On the algebra of logic”. 《American Journal of Mathematics》 (영어) 3 (1): 15–57. JFM 12.0041.01. JSTOR 2369442. 
  5. Aitken, A. C. (1933). “A problem in combinations”. 《Edinburgh Mathematical Notes》 (영어) 28: 18–23. doi:10.1017/S1757748900002334. JFM 59.0937.01. Zbl 0007.38907. 
  6. Ramanujan, Srinivasa (1957). 《Notebooks Vol. 2》 (영어). 뭄바이: Tata Institute of Fundamental Research. 
  7. Berndt, Bruce C. (2011년 4월). “Ramanujan reaches his hand from his grave to snatch your theorems from you” (PDF). 《Asia Pacific Mathematics Newsletter》 (영어) 1 (2): 8–13. 
  8. Bell, E. T. (1934). “Exponential polynomials”. 《Annals of Mathematics》 (영어) 35: 258–277. JFM 60.0295.01. JSTOR 1968431. Zbl 0009.21202. 
  9. Touchard, Jacques (1939). “Sur les cycles des substitutions”. 《Acta Mathematica》 70 (1): 243–297. doi:10.1007/BF02547349. ISSN 0001-5962. MR 1555449. 

외부 링크편집