Numer dzwonka

W matematyce , n- th liczba Bell (nazwany Eric Temple Bell ) to numer partycji z zestawu z n różnych elementów lub, co sprowadza się do tego samego, liczba relacja równoważności w takim zestawie.

Pierwsze właściwości

Liczby te tworzą ciąg liczb całkowitych A000110 z OEIS , którego pierwsze wyrazy można obliczyć ręcznie: $B_ {0} = 1, \ quad B_ {1} = 1, \ quad B_ {2} = 2, \ quad B_ {3} = 5, \ quad B_ {4} = 15, \ quad B_ {5} = 52, \ quad B_ {6} = 203, \ quad B_ {7} = 877, \ quad \ ldots$ Pierwsza ma wartość 1, ponieważ istnieje dokładnie jedna partycja pustego zbioru : pusta partycja, nie składająca się z żadnych części. Rzeczywiście, jego elementy (ponieważ nie ma żadnego) są rzeczywiście niepuste i rozłączne dwa po dwa i są puste.
Te partycje są , a trzy partycje typu . ${\ styl wyświetlania B_ {3} = 5}$ $\{ABC\}$ ${\ styl wyświetlania \ {\ {a \}, \ {b \}, \ {c \} \}}$ ${\ styl wyświetlania \ {\ {a, b, c \} \}}$ ${\ styl wyświetlania \ {\ {a \}, \ {b, c \} \}}$
Numery Bell można również obliczyć krok po kroku przez stosunku nawrotu poniżej, czasami zwane „Powiązania Aitken ” w rzeczywistości z powodu japońskiego matematyka z XVIII -tego wieku Yoshisuke Matsunaga: $B _ {{n + 1}} = \ suma _ {{k = 0}} ^ {{n}} {n \ wybierz k} B_ {k},$ co można zademonstrować w następujący sposób:
Po ustaleniu elementu x w zestawie n + 1 elementów, sortujemy przegrody według liczby k elementów poza częścią zawierającą x .
Dla każdej wartości k od 0 do n konieczne jest zatem wybranie k elementów spośród n elementów różnych od x , a następnie dokonanie podziału.
Siedem mniejsza liczba Bell pierwszy są B 2 = 2, B 3 = 5, B 7 = 877, B 13 = 27644437, B 42 = 35 742 549 198 872 617 291 353 508 656 626 642 567, B 55 = 359 334 085 968 622 831 041 960 188 598 043 661 065 388 726 959 079 837 i B 2841 (patrz apartamenty A051131 i A051130 OEIS). Nie wiadomo, czy są inne.

Seria generatorów

Aby obsłużyć wszystkie liczby Bella, możemy spojrzeć na powiązany generator i szereg generatorów wykładniczych , które są odpowiednio:

G (X) = \ suma _ {n} B_ {n} X ^ {n} {\ tekst {i}} E (X) = \ suma _ {n} {\ frac {B_ {n}} {n! }} X ^ {n} = 1 + X + 2 {\ frac {X ^ {2}} {2!}} + 5 {\ frac {X ^ {3}} {3!}} + 15 {\ frac {X ^ {4}} {4!}} + \ Ldots

Pierwszym z nich jest na przykład używane do badania kongruencji zajęcia z . Jeśli chodzi o drugi szereg formalny , spełnia on równanie różniczkowe : można to zobaczyć pisząc wzór rekurencyjny w postaci $B_ {n}$ $E '(X) = {\ matematyka {e}} ^ {X} E (X)$

{\ displaystyle {\ frac {B_ {n + 1}} {n!}} = \ suma _ {k + l = n} {\ frac {1} {k!}} {\ frac {B_ {l}} {l!}} ~.}

Wywnioskujemy, że jest równa stałej multiplikatywnej w pobliżu (którą znajdujemy identyfikując wyraz stały): ${\ matematyka {e}} ^ {{{\ matematyka {e}} ^ {X}}}$

E (X) = {\ matematyka {e}} ^ {{{\ matematyka {e}} ^ {X} -1}}.

Identyfikacja współczynników prowadzi do wzoru Dobińskiego :

B_ {n} = {\ frac {1} {{\ matematyka {e}}}} \ suma _ {{k = 0}} ^ {\ infty} {\ frac {k ^ {n}} {k!} }

który to moment rzędu n o rozkład Poissona z parametrem 1.

Inne właściwości

Spełniają również zgodność Toucharda : jeśli p jest dowolną liczbą pierwszą, to

B _ {{p + n}} \ równoważ B_ {n} + B _ {{n + 1}} \ mod s.

Każda liczba Bell jest sumą liczb Stirlinga drugiego rodzaju :

{\ displaystyle B_ {n} = \ suma _ {k = 0} ^ {n} S (n, k) = \ suma _ {k = 0} ^ {n} \ lewo \ {{\ początek {macierz} n \\ k \ end {matryca}} \ prawa \}.}

Znanych jest kilka asymptotycznych wzorów na liczby Bella; jeden z nich jest

B_ {n} \ sim {\ frac {1} {{{\ sqrt n}}}} \ po lewej [{{\ frac {n} {W (n)}} \ po prawej] ^ {{n + {\ frac {1} {2}}}} e ^ {{{\ frac {n} {W (n)}} - n-1}},

gdzie W jest funkcją W Lamberta ; uzyskuje się mniej dokładne przybliżenie, ale wygodniejsze w użyciu, za pomocą kadrowania ; można też zauważyć podobieństwo poprzedniego przybliżenia do formuły Stirlinga . $\ ln x- \ ln \ ln x <W (x) <\ ln x$

Zobacz również

Te numery Bell zamawiane , które identyfikują zamówionego partycje.
Trójkąt Bell , który pozwala w prosty sposób uzyskać numery Bell

Uwagi i referencje

Elementy zestawu są zawsze różni się w zwykłej teorii zbiorów , ale nie jest to w przypadku MULTISET teorii . A liczba podziałów zbioru z n nierozróżnialnymi elementami jest liczbą podziałów liczby całkowitej .
(w) AC Aitken , „ Problem w kombinacjach ” , Uwagi matematyczne , t. 28,Styczeń 1933, xviii – xxiii ( ISSN 1757-7489 i 2051-204X , DOI 10.1017/S1757748900002334 , czytanie online , dostęp 29 maja 2021 )
Donald Knuth , Sztuka programowania komputerowego : historia generacji kombinatorycznej , t. 4, faks. 4, Addisona Wesleya,2010
Daniel Barsky i Bénali Benzaghou , „ Liczby dzwonów i suma silni ”, Journal de Théorie des Nombres de Bordeaux , tom. 16,2004, s. 1-17 ( przeczytaj online [PDF] )
Znajdziemy inne przybliżenia B n na (w) Eric W. Weisstein , " Bell Number " na MathWorld .

Bibliografia

Donald Knuth , Sztuka programowania komputerowego : Historia generacji kombinatorycznej , t. 4, faks. 3, Addisona Wesleya,2010