종 번호

조합 수학에서 벨 번호는 세트의 가능한 파티션을 계산한다. 이 숫자들은 19세기부터 수학자들에 의해 연구되어 왔으며, 그 뿌리는 중세 일본으로 거슬러 올라간다.^[1] 스티글러의 에포니미 법칙의 예에서 1930년대에 이들에 대해 쓴 에릭 템플 벨의 이름을 따온 것이다.

벨 번호는 B로_n 표시되며, 여기서 n은 0보다 크거나 같은 정수다. B₀ = B₁ = 1로 시작하여, 처음 몇 개의 벨 번호는

1, 1, 2, 5, 15, 52, 203, 877, 4140, ...(OEIS에서 연속 A000110).

벨 번호 B는_n 정확히 n개의 요소가 있는 세트를 분할하는 여러 가지 방법 또는 동등하게 동등한 관계 수를 계산한다. B는_n 또한 n행시에 대한 다른 운율의 수를 계산한다.^[2]

이 숫자들은 계산 문제에서 나타나는 것뿐만 아니라 확률 분포의 순간으로서 다른 해석을 가지고 있다. 특히 B는_n 평균이 1인 포아송 분포의 n번째 모멘트다.

계산

파티션 설정

일반적으로 B는_n n 크기 집합의 파티션 수입니다. 집합 S의 파티션은 결합이 S인 S의 비어 있지 않은 쌍으로 분리된 하위 집합으로 정의된다. 예를 들어, 3-element set {a, b, c}은(는) 5개의 고유한 방법으로 분할할 수 있기 때문에 B₃ = 5:

{a}, {b}, {c} }

{a}, {b, c} }

{b}, {a, c} }

{c}, {a, b} }

{a, b, c} }.

위의 정해진 표기법에서 제안된 바와 같이, 가족 내에서 하위 집합의 순서는 고려되지 않고, 순서 파티션은 순서된 벨 번호의 다른 순서에 의해 계수된다. 빈 세트의 파티션이 정확히 하나 있기 때문에 B는₀ 1이다. 이 파티션은 그 자체로 빈 집합이다. 0개의 하위 집합으로 구성된 빈 집합의 하위 집합으로 해석될 수 있다. 이 계열의 모든 하위 집합이 빈 집합의 비어 있지 않은 하위 집합이며, 이러한 있음직하지 않은 속성을 가질 하위 집합이 없기 때문에 빈 집합의 쌍으로 분리된 하위 집합이라는 것은 공허한 사실이다.

집합의 분할은 1 대 1과 동등성 관계에 대응한다. 이것들은 반사적이고, 대칭적이며, 전이적인 이항 관계다. 파티션에 해당하는 동등성 관계에서는 두 요소가 서로 동일한 파티션 하위 집합에 속할 때 두 요소가 동등하다고 정의한다. 반대로 모든 동등성 관계는 동등성 등급의 분할에 해당한다.^[3] 따라서 벨 번호도 동등성 관계를 계산한다.

인자화

숫자 N이 제곱이 없는 양의 정수(일부 고유 소수 n의 산물이라는 의미)인 경우, B는_n N의 서로 다른 승수 파티션 수를 제공한다. 이들은 N을 1보다 큰 숫자로 인자화한 것으로, 두 인자화가 서로 다른 순서로 동일한 인자를 갖는 경우 동일한 인자로 취급한다.^[4] 예를 들어, 30은 세 개의 소수 2, 3, 5의 곱이며 B = 5 인자를₃ 가지고 있다.

${\displaystyle 30=2\board 15=3\board 10=5\board 6=2\board 3\board 5}$

운율 체계

벨 숫자들은 또한 n행시나 연자의 운율 체계도 세어준다. 운율 체계는 어떤 선들이 서로 운을 맞추는지 묘사하고 있으며, 따라서 선들의 집합이 운율 하위 집합으로 분할되는 것으로 해석될 수 있다. 운율 체계는 보통 로마자 서열로 쓰여지는데, 한 줄에 한 줄씩, 운율 선은 서로 같은 문자를 주고, 각 운율의 첫 번째 선은 알파벳순으로 라벨을 붙인다. 따라서 15개의 가능한 4행 운율 체계로는 AAAA, AAAB, AABA, AABB, AABB, ABA, ABA,^[2] ABA, ABA, ABBB, ABC, ABC, ABCA, ABCA, ABCBBBB, ABC, ABCBBBBBB, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC, ABC

순열

벨 번호는 가드너 부록(1978년)에 언급된 카드 섞기 문제에서 나온다. 상단 카드를 제거하고 데크(데크 상단의 원래 위치를 포함)의 어느 곳에 재삽입하여 데크에 패를 반복하여 패를 끼우면 이 작업을 정확히 n번 반복하여 다른 패를ⁿ 끼울 수 있다. 이 중 갑판을 원래의 정렬된 순서로 되돌리는 숫자는 정확히 B이다_n. 따라서 갑판을 이런 식으로 분리한 후 갑판이 원래 순서에 있을 확률은_n B/n이며ⁿ, 갑판의 균일한 무작위 순열을 설명하는 1/n 확률보다 상당히 크다.

카드 섞기와 관련된 몇 가지 다른 문제들은 벨 번호로도 응답되는 특별한 종류의 순열들을 세는 것이다. 예를 들어, n번째 벨 번호는 정렬된 3개의 값이 이 3개의 항목 중 마지막 2개를 연속해서 가지지 않는 n개 항목의 순열 수와 같다. 연속해야 하는 값이 서로 인접해 있고 연속적이지 않게 보일 수 있는 값이 대시에 의해 분리되는 일반화된 순열 패턴에 대한 표기법에서 이러한 순열은 패턴 1-23을 피하는 순열로 설명할 수 있다. 일반화된 패턴 12-3, 32-1, 3-21, 1-32, 3-12, 21-3, 23-1을 피하는 순열도 벨 번호로 계산한다.^[5] 321개 패턴(연속 값 제한 없음)마다 3241개 패턴으로 확장할 수 있는 순열도 벨 번호로 계산한다.^[6] 그러나 벨 수는 너무 빨리 늘어나서 이런 식으로 일반화되지 않은 패턴을 피하는 순열 수를 셀 수 없다: (현재는 증명된) 스탠리-윌프 추측에 의해 그러한 순열의 수는 단독적으로 지수적이며, 벨 숫자는 그보다 더 높은 점증적 성장률을 보인다.

계산을 위한 삼각형 구조

벨 번호는 알렉산더 아이트켄과 찰스 샌더스 피르체 다음에 아이트켄의 배열 또는 페어체 삼각형이라고도 불리는 이른바 벨 삼각형을 만들어 쉽게 계산할 수 있다.^[7]

1. 1번부터. 이 항목을 직접 행에 놓으십시오. ( ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle 1}$ =$$1 {\$displaystyle x_{0,1$}=1$\})$
2. 이전 행에서 가장 오른쪽 요소를 가장 왼쪽 숫자로 새 행을 시작하십시오(${\displaystyle {}_{}}$,${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$- ${\displaystyle 1_{}}$,${\displaystyle r_{}}$ ${\$왼쪽 $화살표 x_{i-1,r}).$ 여기서$$ r은 (i-1)-번째 행의 마지막 요소임
3. Determine the numbers not on the left column by taking the sum of the number to the left and the number above the number to the left, that is, the number diagonally up and left of the number we are calculating ${\displaystyle (x_{i,j}\leftarrow x_{i,j-1}+x_{i-1,j-1})}$
4. 이전 행보다 숫자가 하나 더 많은 새 행이 있을 때까지 3단계를 반복하십시오($j{\displaystyle }$= ${\displaystyle r}$+ ${\displaystyle 1}$ ${\displaystyle j=r+1}$까지 3단계 수행$).$
5. 지정된 행의 왼쪽에 있는 번호는 해당 행의 벨 번호 입니다$.$ (${\displaystyle {\mathrm{Bi}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {i,}_{}}$ 1 ${\$ 화살표 $x_{i,1})$

다음은 이러한 규칙에 의해 구성된 삼각형의 처음 다섯 행이다.

 1  1   2  2   3   5  5   7  10  15 15  20  27  37  52 

벨 번호는 삼각형의 왼쪽과 오른쪽 양쪽에 나타난다.

특성.

합계 공식

벨 번호는 이항 계수와 관련된 반복 관계를 만족한다.^[8]

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

n + 1 항목의 임의 파티션에서 첫 번째 항목이 포함된 세트를 제거하면 0에서 n까지의 범위가 될 수 있는 일부 숫자 k에 대해 더 작은 k 항목 집합의 파티션이 남는다는 것을 관찰함으로써 설명할 수 있다. 한 세트를 제거한 후에도 남아 있는 k 항목에 대한${\displaystyle }$(${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{k}{}}$) ${\$ 선택$$ 사항과 파티션 분할 방법에 대한 B 선택_k 항목이 있다.

다른 합계 공식은 두 번째 종류의 스털링 번호의 합으로 각 벨 번호를 나타낸다.

${\displaystyle B_{n}=\sum _{k=0}^{n}\왼쪽\{n \atop k}\오른쪽\}.}$

스털링 번호${\displaystyle }${${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{k}{}}$ ${\displaystyle \}}$ ${\$\n \$atop$ k$}\right\}}$은 일련의 카디널리티 n을 정확히 비어 있지 않은 하위 집합으로 분할하는 방법의 수입니다$$. 따라서 벨 번호와 스털링 숫자와 관련된 방정식에서, 방정식의 왼쪽에 계산된 각 칸막이는 오른쪽의 합계의 정확히 하나의 항으로 계산되며, k는 칸막이에 있는 집합의 수입니다.^[9]

스피비(2008)는 이 두 가지 합계를 모두 합친 공식을 제공했다.

${\displaystyle B_{n+m}=\sum _{k=0}^{n}\sum _{j=0}^{m}\{m \atop j}\right\}{n \n \n 선택 k}j^{n-k}B_{k}.}$

생성함수

벨 번호의 지수 생성 함수는

${\displaystyle B(x)=\sum _{n=0}^{\inflt }{\frac {B_{n}}{n!}}}x^{n}=e^{e^{x}-1.}$

이 공식에서 가운데의 합계는 숫자의 모든 순서에 대한 지수 생성 함수를 정의하기 위해 사용되는 일반적인 형식이며, 오른쪽의 공식은 벨 번호의 특정 경우에 합계를 수행한 결과물이다.

이 결과를 도출하는 한 가지 방법은 분석 결합기법을 사용하는데, 수학 추론의 한 형태는 수학적 사물의 집합이 단순한 물체로부터 그 구조를 설명하는 공식에 의해 설명되고, 그 다음 그 공식들을 조작하여 물체의 결합기적 특성을 도출하는 것이다. 분석 조합 언어에서, 세트 파티션은 1에서 n까지 라벨이 표시된 요소들이 분포된 비어 있지 않은 항아리 집합으로 설명될 수 있으며, 모든 파티션의 조합 클래스는 (모든 n에 대해) 표기법으로 표현될 수 있다.

${\displaystyle \mathrm {S\scriptstyle ET}(\mathrm {S\scriptstyle ET} _{\geq 1}({\mathcal {Z})).}$

여기서 $Z{\displaystyle \mathcal{}}$ ${\$은 크기가$$ 1인 단일 멤버만 있는 조합 클래스, 단지에 넣을 수 있는 요소다. 내부 $S{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {E\mathrm{}}_{}}$ ${\displaystyle {\mathrm{T}}_{}}$ ${\displaystyle {\ge }_{}}$ ${\displaystyle 1_{}}$ ${\$1} 연산자는$$ 하나 이상의 라벨로 표시된 요소를 포함하는 세트 또는 urn을 설명하며, $외부{\displaystyle \mathrm{}}$ S E ${\displaystyle \mathrm{T}}$ ${\$은 이러한 항아리 집합으로 전체 파티션을 설명한다$$. 그런 다음 S ${\displaystyle E\mathrm{}}$ ${\displaystyle \mathrm{T}}$ ${\$ 연산자를$$ 지수 함수로 변환하고 비빈도 제약 조건 11을 하나씩 뺄셈으로 변환하여 지수 생성 함수를 이 표기법에서 읽을 수 있다.^[10]

동일한 생성함수를 도출하기 위한 다른 방법은 지수 생성함수가 미분 방정식 $B{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$( ${\displaystyle x}$)${\displaystyle }$= e ${\displaystyle x^{}}$ ${\displaystyle {}^{}}$(${\displaystyle }$x ) ${\displaystyle B'(x)=e^{x}B(x)}$을 만족한다는 것을 보여주기 위해 이항계수 측면에서 벨 숫자에 대한 재발 관계를 사용한다$.$ 함수 자체는 이 방정식을 풀면 알 수 있다.^[11][12][13]

확률 분포의 모멘트

벨 번호는 도빈스키의 공식을^[14][11][13] 만족시킨다.

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

이 공식은 지수함수에 대해 Taylor 시리즈를 사용하여 지수 생성 함수를 확장한 다음 동일한 지수로 항을 수집하여 도출할 수 있다.^[10] B를_n 기대값 1을 갖는 포아송 분포의 n번째 모멘트로 해석할 수 있다.

n번째 벨 번호는 또한 n번째 완전한 벨 다항식의 계수의 합으로, 확률 분포의 n번째 모멘트를 첫 번째 적혈구의 함수로 표현한다.

모듈식 산술

벨 번호는 터치카드의 일치에 따른다. 만약^[15] p가 어떤 프라임 숫자라면.

${\displaystyle B_{p+n}\equiv B_{n}+B_{n+1}{\pmod {p}}$

또는^[16] 일반화

${\displaystyle B_{p^{m}+n}\equiv mB_{n}+{n}+B_{n+1}{\pmod {p}}.}$

Touchard의 일치 때문에, 벨 번호는 모든 p 프라임 번호에 대해 주기적인 모듈로 p이다. 예를 들어, p = 2와 같이, 벨 번호는 3주기에도 홀수-오드 패턴을 반복한다. 이 반복의 기간은 임의의 소수 p에 대해, 반드시 divisor가 되어야 한다.

${\displaystyle {\frac {p^{p1}-1}{p-1}$

그리고 모든 프라임 p 101 101과 p = 113, 163, 163, 167 또는 173에 대해 정확히 이 숫자다(OEIS에서 순서 A001039).^[17][18]

벨 번호에서 모듈로 n까지의 기간은

1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, 25239592216021, 411771, 10153, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784341, 85593501183, 949112181811268728834319677753, 312, 3905, 75718776648063, 117, 1647084, 91703076898614683377208150526107718802981, 30459, 568972471024107865287021434301977158534824481, 96, 3709051793, 155107549103688143283, 107197717, 156, ...(OEIS에서 시퀀스 A054767)

적분표현

지수 생성 함수에 Cauchy의 적분 공식을 적용하여 복잡한 적분 표현을 산출한다.

${\displaystyle B_{n}={\frac {n!}}{2\pi ee}\int _{\frac {e^{e^{z}}{z^{n+1}}\,dz.}$

일부 무증상 표현은 가장 가파른 하강 방법을 표준으로 적용함으로써 도출될 수 있다.^[19]

로그 일치성

벨 번호는 대수적으로 볼록한 순서를 형성한다. 요인_n B/n!으로 나누면 로그 오목한 순서가 나온다.^[20][21][22]

성장률

벨 번호에 대한 몇 가지 점증적 공식은 알려져 있다. 베렌드&타사(2010)에서는 다음과 같은 한계가 설정되었다.

${\$$^{n}}$ 모든 양의 $정수$ n ${\displaystyle$ n$\};$

더욱이 > ${\displaystyle \varepsilon >0}$일 경우, 모든 > () ${\displaystyle n>>n_{0}(\varipsilon )}$에 대해

${\displaystyle B_{n}<\frac {e^{-0.6+\varepsilon }{\ln(n+1)}\오른쪽)^{n}}}$

where ${\displaystyle ~n_{0}(\varepsilon )=\max \left\{e^{4},d^{-1}(\varepsilon )\right\}~}$ and ${\displaystyle ~d(x):$$=\ln \ln(x+1)-\ln \ln$\ln$x+{1+e^{-1$}{\$ln x}\,}$ 로그와 동일한 증가율을 갖는 함수인 램버트 W 함수를 사용하여$$ 벨 번호를 근사하게 추정할 수도 있다.

${\displaystyle B_{n}\sim {1}{\frac {1}{\sqrt{n}}\왼쪽({\frac {n}{W(n)}}\오른쪽)^{n+{\frac {1}{1}:{2}}:\exp \left({\frac {n}{W(n)}}}-n-1\right)}$

Moser & Wyman(1955)은 확장을 설립했다.

${\displaystyle B_{n+h}={\frac {(n+h)!}{W(n)^{n+h}}\time {\frac {\exp(e^{W(n)-1)}{{1/2}}회\time \refac(1+{P_{0}+hP_{1}+h^{2}P_{1}:{e^{W(n)}}}+{\frac {Q_{0}+hQ_{1}+h^{2}}}Q_{2}+h^{3}}Q_{3}+h^{4}}Q_{4}}}{e^{2W(n)}}}+O(e^{-3W(n)}}\오른쪽)}}$

uniformly for ${\displaystyle h=O(\ln(n))}$ as ${\displaystyle n\rightarrow \infty }$, where ${\displaystyle B}$ and each ${\displaystyle P_{i}}$ and ${\displaystyle Q_{i}}$ are known expressions in ${\displaystyle W(n)}$.^[24]

점증적 표현

${\displaystyle {\begin{aligned}{\frac {\ln B_{n}}{n}}&=\ln n-\ln \ln n-1+{\frac {\ln \ln n}{\ln n}}+{\frac {1}{\ln n}}+{\frac {1}{2}}\left({\frac {\ln \ln n}{\ln n}}\right)^{2}+O\left({\frac {\ln \ln n}{(\ln n)^{2}}}\right)\\&{}\qquad {\text{as }n\\to \inflineed}}}$

드 브뤼옌(1981년)에 의해 설립되었다.

벨 프라임즈

가드너(1978)는 무한히 많은 벨 숫자도 소수인가 하는 문제를 제기했다. Bell의 주요 숫자는 다음과 같다.

2, 5,877, 276444437, 357425491988726171353508656626642567, 35933408596862283104196018980436610653899079837(OEIS의 후속 A051131)

지수 2, 3, 7, 13, 42 및 55에 해당된다(OEIS에서 순차 A051130).

다음 벨 프라임은 B이며, 대략 9₂₈₄₁.30740105 × 10이다⁶⁵³⁸.^[25] 2018년^[update] 현재, 가장 큰 프라임 벨 번호로 알려져 있다. 이그나시오 라로사 카네스트로는 그것이 2002년에 일어날 가능성이 있는 전성기임을 보여주었다. 마르셀 마틴의 ECPP 프로그램 프리모를 17개월간 연산해 본 이그나시오 라로사 카네스트로는 2004년에 그것이 전성기임을 증명했다. 그는 Eric Weisstein에 의해 B까지₃₀₄₄₇ 확장된 B 아래의₆₀₀₀ 다른 가능한 모든 것을 배제했다.^[26] 수색은 바츨라프 코테소베크(05/18/2021)에 의해 B까지₅₀₀₀₀ 연장되었다.

역사

벨 번호는 에릭 템플 벨이 1938년에 벨 다항식들을 연구한 1934년 논문을 따라 쓴 글에서 따온 것이다.^[27][28] 벨은 이 숫자들을 발견했다고 주장하지 않았다; 그는 1938년 논문에서 벨의 숫자가 "자주 조사되었고" "여러 번 재발견되었다"고 썼다. 벨은 이러한 숫자에 대해 몇 개의 초기 간행물을 인용하는데, 도비셰스키(1877년)는 도비셰스키의 벨 번호 공식을 제공한다. 벨은 이 숫자들을 "우수한 숫자"라고 불렀고, 이 숫자들의 이름인 "벨 번호"와 표기법_n B는 베커와 리오르단 (1948)에 의해 그들에게 주어졌다.^[29]

세트 칸막이의 첫 번째 철저한 열거는 중세 일본에서 일어난 것으로 보이는데, 그 곳에서 (겐지 이야기라는 책의 인기에 자극받아) 겐지코라는 응접실 게임이 등장했는데, 손님들에게 냄새 맡기기 위해 향 다섯 봉지를 주고, 어떤 것이 서로 같으며 어떤 것이 다른 것인지 추측해 보라는 것이었다. 벨 번호 B에₅ 의해 계수된 52개의 가능한 해결책은 52개의 다른 도표에 의해 기록되었는데, 그것은 <겐지 이야기> 일부 판의 제목 위에 인쇄되었다.^[30][31]

스리니바사 라마누잔의 두 번째 수첩에서 그는 벨 다항식 번호와 벨 번호를 모두 조사했다.^[32] 양쪽에 벨 번호가 있는 벨 삼각형의 초기 참고문헌에는 페어체(1880)와 아이트켄(1933)이 있다.

참고 항목

• Touchard 다항식
• 카탈루냐 수

메모들

참조

외부 링크

• Robert Dickau. "Diagrams of Bell numbers".
• Weisstein, Eric W. "Bell Number". MathWorld.
• Gottfried Helms. "Further properties & Generalization of Bell-Numbers" (PDF).