Bell číslo

V matematice je n- té číslo Bell (pojmenované podle Erica Temple Bell ) počet oddílů množiny s n odlišnými prvky nebo, co se rovná stejné, počet vztahů ekvivalence na takové množině.

První vlastnosti

Tato čísla tvoří posloupnost celých čísel A000110 z OEIS , jejichž první členy lze vypočítat ručně: $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$ První má hodnotu 1, protože v prázdné sadě je přesně jeden oddíl : prázdný oddíl, který není tvořen žádnými částmi. Ve skutečnosti jsou jeho prvky (protože žádné nejsou) skutečně neprázdné a nesouvislé dva po druhém a prázdné unie.
Tyto oddíly jsou , a tři oddíly typu . ${\ displaystyle B_ {3} = 5}$ $\ {ABC \}$ ${\ displaystyle \ {\ {a \}, \ {b \}, \ {c \} \}}$ ${\ displaystyle \ {\ {a, b, c \} \}}$ ${\ displaystyle \ {\ {a \}, \ {b, c \} \}}$
Čísla Bell lze také vypočítat krok za krokem ze strany vztahu opakování následuje, někdy nazývané „Vztah Aitken “ a ve skutečnosti vzhledem k japonskému matematik z XVIII -tého století Yoshisuke Matsunaga: $B _ {{n + 1}} = \ součet _ {{k = 0}} ^ {{n}} {n \ vyberte k} B_ {k},$ což lze demonstrovat následovně:
Po opravě prvku x v sadě s prvky n + 1 roztřídíme oddíly podle počtu k prvků mimo část obsahující x .
Pro každou hodnotu k od 0 do n je proto nutné zvolit k prvků mezi n prvky odlišnými od x , poté dát oddíl.
Sedm menší počty Bell první jsou 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 a B 2841 (viz apartmá A051131 a A051130 OEIS). Není známo, zda existují i další.

Řada generátorů

Abychom zvládli všechna čísla Bell, můžeme se podívat na přidružený generátor a řadu exponenciálních generátorů , které jsou:

G (X) = \ sum _ {n} B_ {n} X ^ {n} {\ text {a}} E (X) = \ sum _ {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

Prvním z nich je například použit ke studiu shodu tříd z . Pokud jde o druhou formální řadu , splňuje diferenciální rovnici : lze to vidět napsáním vzorce opakování do formuláře $B_ {n}$ $E '(X) = {\ mathrm {e}} ^ {X} E (X)$

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

Dedukujeme, že se rovná multiplikativní konstantě blízké (kterou zjistíme identifikací konstantního členu): ${\ mathrm {e}} ^ {{{\ mathrm {e}} ^ {X}}}$

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

Identifikace koeficientů vede k Dobinského vzorci :

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

což je okamžik řádu n části Poissonova rozdělení s parametrem 1.

Další vlastnosti

Také uspokojují shodu Touchard : pokud p je jakékoli prvočíslo, pak

B _ {{p + n}} \ ekviv B_ {n} + B _ {{n + 1}} \ mod str.

Každé Bell číslo je součtem Stirlingových čísel druhého druhu :

{\ displaystyle B_ {n} = \ součet _ {k = 0} ^ {n} S (n, k) = \ součet _ {k = 0} ^ {n} \ vlevo \ {{\ začátek {matice} n \\ k \ end {matrix}} \ right \}.}

Je známo několik asymptotických vzorců pro Bellova čísla; jedním z nich je

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

kde W je Lambertova W funkce ; získá se méně přesná aproximace, ale pohodlnější použití s pomocí rámování ; lze si také všimnout podobnosti předchozí aproximace se Stirlingovým vzorcem . $\ ln x- \ ln \ ln x <W (x) <\ ln x$

Podívejte se také

Tyto čísla Bell objednané , které identifikují objednané oddílů.
Bell trojúhelník , který vám umožní jednoduše získat čísla Bell

Poznámky a odkazy

Prvky množiny se v obvyklé teorii množin vždy liší , ale v teorii multisetů tomu tak není . A počet oddílů sady s n nerozlišitelnými prvky je počet oddílů celého čísla .
(in) AC Aitken , „ Problém v kombinacích “ , Matematické poznámky , sv. 28,Leden 1933, xviii - xxiii ( ISSN 1757-7489 a 2051-204X , DOI 10.1017 / S1757748900002334 , číst online , přístup 29. května 2021 )
Donald Knuth , The Art of Computer Programming : History of Combinatorial Generation , sv. 4, fasc. 4, Addison Wesley,2010
Daniel Barsky a Bénali Benzaghou , „ Bell Bell and Sum of Factorials “, Journal de Théorie des Nombres de Bordeaux , sv. 16,2004, str. 1–17 ( číst online [PDF] )
Další aproximace najdeme B n na (v) Ericovi W. Weissteinovi , „ Bell Number “ na MathWorld .

Bibliografie

Donald Knuth , The Art of Computer Programming : History of Combinatorial Generation , sv. 4, fasc. 3, Addison Wesley,2010