Bell číslo - Bell number

v kombinatorická matematika, Čísla zvonků spočítat možné oddíly sady. Tato čísla studovali matematici od 19. století a jejich kořeny sahají až do středověkého Japonska. V příkladu Stiglerův zákon eponymie, jsou pojmenovány po Eric Temple Bell, který o nich psal ve 30. letech.

Čísla Bell jsou označena B_n, kde n je celé číslo větší nebo rovno nula. Začínání s B₀ = B₁ = 1, prvních několik čísel Bell je

1, 1, 2, 5, 15, 52, 203, 877, 4140, ... (sekvence A000110 v OEIS ).

Bell číslo B_n spočítá počet různých způsobů rozdělení sady, která má přesně n počet prvků nebo ekvivalentně počet ekvivalenční vztahy na to. B_n také počítá počet různých rýmová schémata pro n-line básně.^[1]

Kromě toho, že se tato čísla objevují při počítání problémů, mají i jinou interpretaci momenty z rozdělení pravděpodobnosti. Zejména, B_n je nČtvrtý okamžik Poissonovo rozdělení s znamenat 1.

Počítací

Nastavit oddíly

Oddíly sad lze uspořádat v částečném pořadí, což ukazuje, že každý oddíl sady velikosti n "používá" jeden z oddílů sady velikosti n-1.

52 oddílů sady s 5 prvky

Obecně, B_n je počet oddíly sady velikosti n. Oddíl sady S je definována jako sada neprázdných, párových disjunktních podmnožin S jehož svazek je S. Například, B₃ = 5, protože sada 3 prvků {A, b, C} lze rozdělit na 5 různých způsobů:

{ {A}, {b}, {C} }

{ {A}, {b, C} }

{ {b}, {A, C} }

{ {C}, {A, b} }

{ {A, b, C} }.

B₀ je 1, protože v systému Windows je právě jeden oddíl prázdná sada. Každý člen prázdné sady je neprázdná sada (tj prázdně pravda ) a jejich unie je prázdná množina. Prázdná sada je tedy jediným oddílem sama o sobě. Jak navrhuje výše uvedená sada notace, neuvažujeme ani o pořadí bloků v oddílu, ani o pořadí prvků v každém bloku. To znamená, že následující oddíly jsou považovány za identické:

{ {b}, {A, C} }

{ {A, C}, {b} }

{ {b}, {C, A} }

{ {C, A}, {b} }.

Pokud se místo toho za různé oddíly považují různá uspořádání sad, pak počet těchto objednané oddíly je dán objednal Bell čísla.

Faktorizace

Pokud číslo N je bez čtverce pozitivní celé číslo (což znamená, že se jedná o produkt určitého čísla n výrazných prvočísla ), pak B_n udává počet různých multiplikativní oddíly z N. Tyto jsou faktorizace z N do čísel větších než jedna, přičemž dvě faktorizace jsou považovány za stejné, pokud mají stejné faktory v jiném pořadí.^[2] Například 30 je produktem tří prvočísel 2, 3 a 5 a má B₃ = 5 faktorizací:

${ displaystyle 30 = 2 krát 15 = 3 krát 10 = 5 krát 6 = 2 krát 3 krát 5}$

Rýmová schémata

Čísla Bell také počítají rýmová schémata z n-čára báseň nebo sloka. Schéma rýmu popisuje, které řádky se rýmují navzájem, a proto je lze interpretovat jako rozdělení sady řádků do rýmovaných podmnožin. Schémata rýmů jsou obvykle psána jako posloupnost římských písmen, jedno na řádek, přičemž rýmované řádky dostávají stejné písmeno jako ostatní a první řádky v každé sadě rýmů jsou označeny v abecedním pořadí. Tedy 15 možných čtyřřádkových schémat rýmů je AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC a ABCD.^[1]

Permutace

Čísla Bellů se objevují na kartě míchání problém zmíněný v dodatku k Gardner (1978). Pokud je balíček n karty jsou zamíchány opakovaným vyjímáním horní karty a jejím opětovným vložením kdekoli v balíčku (včetně původní polohy v horní části balíčku), s přesně n opakování této operace, pak existují nⁿ různé míchání, které lze provést. Z nich je číslo, které vrátí balíček do původního seřazeného pořadí, přesně B_n. Pravděpodobnost, že balíček je po jeho náhodném promíchání v původním pořadí, je tedy B_n/nⁿ, který je výrazně větší než 1 /n! pravděpodobnost, která by popisovala rovnoměrně náhodnou permutaci paluby.

S mícháním karet souvisí několik dalších problémů počítání speciálních druhů obměny na které také odpovídají čísla Bell. Například nČíslo Bell se rovná počtu permutací n položky, ve kterých žádné tři hodnoty, které jsou v seřazeném pořadí, nemají poslední dvě z těchto tří po sobě jdoucích. V notaci pro zobecněné permutační vzory kde hodnoty, které musí následovat, se zapisují vedle sebe a hodnoty, které se mohou objevit po sobě, jsou odděleny pomlčkou, lze tyto permutace popsat jako permutace, které se vyhýbají vzoru 1-23. Permutace, které se vyhýbají zobecněným vzorům 12-3, 32-1, 3-21, 1-32, 3-12, 21-3 a 23-1, se také počítají podle Bellových čísel.^[3] Permutace, ve kterých lze každý vzor 321 (bez omezení po sobě jdoucích hodnot) rozšířit na vzor 3241, se také počítají podle čísel Bell.^[4] Čísla Bellů však rostou příliš rychle na to, aby se daly spočítat permutace, které se vyhýbají vzoru, který nebyl zobecněn tímto způsobem: (nyní prokázáno) Domněnka Stanleyho a Wilfa, počet takových permutací je jednotlivě exponenciální a Bellova čísla mají vyšší asymptotickou rychlost růstu.

Trojúhelníkové schéma pro výpočty

Trojúhelníkové pole, jehož pravá úhlopříčná sekvence se skládá z Bellových čísel

Čísla Bell lze snadno vypočítat vytvořením tzv Bell trojúhelník, také zvaný Aitkenovo pole nebo Peirce trojúhelník po Alexander Aitken a Charles Sanders Peirce.^[5]

1. Začněte číslem jedna. Dejte to na řádek sám. (${ displaystyle x_ {0,1} = 1}$)
2. Začněte nový řádek s prvkem zcela vpravo z předchozího řádku jako číslo úplně vlevo (${ displaystyle x_ {i, 1} leftarrow x_ {i-1, r}}$ kde r je poslední prvek (i-1) -th řádek)
3. Určete čísla, která nejsou v levém sloupci, tak, že vezmete součet čísla vlevo a čísla nad číslem vlevo, tj. Číslo úhlopříčně nahoru a nalevo od čísla, které počítáme ${ displaystyle (x_ {i, j} leftarrow x_ {i, j-1} + x_ {i-1, j-1})}$
4. Opakujte krok tři, dokud nebude nový řádek s ještě jedním číslem než předchozí řádek (krok 3 až do ${ displaystyle j = r + 1}$)
5. Číslo na levé straně daného řádku je Bell číslo pro ten řádek. (${ displaystyle B_ {i} leftarrow x_ {i, 1}}$)

Tady je prvních pět řádků trojúhelníku vytvořených těmito pravidly:

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

Čísla zvonků se objevují na levé i pravé straně trojúhelníku.

Vlastnosti

Sčítací vzorce

Čísla Bell splňují a relace opakování zahrnující binomické koeficienty:^[6]

${ displaystyle B_ {n + 1} = součet _ {k = 0} ^ {n} { binom {n} {k}} B_ {k}.}$

To lze vysvětlit pozorováním, že z libovolného oddílu n + 1 položek, odebrání sady obsahující první položku ponechá oddíl menší sady k položky pro nějaké číslo k které se mohou pohybovat od 0 do n. Existují ${ displaystyle { tbinom {n} {k}}}$ možnosti pro k - položky, které zůstanou po odebrání jedné sady, a - B_k možnosti, jak je rozdělit.

Jiný součtový vzorec představuje každé číslo Bell jako součet Stirlingova čísla druhého druhu

${ displaystyle B_ {n} = součet _ {k = 0} ^ {n} vlevo {{n nahoře k} vpravo }.}$

Stirlingovo číslo ${ displaystyle left {{n na vrcholu k} right }}$ je počet způsobů, jak rozdělit sadu mohutnosti n přesně k neprázdné podmnožiny. V rovnici vztahující se k Bellským číslům se Stirlingovými čísly se tedy každý oddíl počítaný na levé straně rovnice počítá přesně v jednom z podmínek součtu na pravé straně, pro který platí k je počet sad v oddílu.^[7]

Spivey (2008) dal vzorec, který kombinuje obě tyto součty:

${ displaystyle B_ {n + m} = součet _ {k = 0} ^ {n} součet _ {j = 0} ^ {m} levý {{m nahoře j} pravý } {n zvolte k} j ^ {nk} B_ {k}.}$

Generující funkce

The exponenciální generující funkce čísel Bell je

${ displaystyle B (x) = součet _ {n = 0} ^ { infty} { frac {B_ {n}} {n!}} x ^ {n} = e ^ {e ^ {x} - 1}.}$

V tomto vzorci je součet ve středu obecnou formou používanou k definování funkce generování exponenciálu pro libovolnou posloupnost čísel a vzorec vpravo je výsledkem provedení součtu v konkrétním případě čísel Bell.

Jeden způsob, jak odvodit tento výsledek používá analytická kombinatorika, styl matematického uvažování, ve kterém jsou sady matematických objektů popsány vzorci vysvětlujícími jejich konstrukci z jednodušších objektů, a poté jsou s těmito vzorci manipulovány za účelem odvození kombinatorických vlastností objektů. V jazyce analytické kombinatoriky lze množinový oddíl popsat jako množinu neprázdného urny do kterých prvků označených od 1 do n byly distribuovány a kombinatorická třída všech oddílů (pro všechny n) lze vyjádřit notací

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

Tady, ${ displaystyle { mathcal {Z}}}$ je kombinatorická třída pouze s jedním členem o velikosti jedna, což je prvek, který lze umístit do urny. Vnitřní ${ displaystyle mathrm {S scriptstyle ET} _ { geq 1}}$ operátor popisuje sadu nebo urnu, která obsahuje jeden nebo více označených prvků a vnější${ displaystyle mathrm {S scriptstyle ET}}$ popisuje celkový oddíl jako soubor těchto urn. Funkce exponenciálního generování může být poté přečtena z této notace překladem ${ displaystyle mathrm {S scriptstyle ET}}$ operátor do exponenciální funkce a omezení neprázdnosti ≥1 do odčítání o jednu.^[8]

Alternativní metoda pro odvození stejné funkce generování používá relaci opakování pro čísla Bell, pokud jde o binomické koeficienty, aby ukázala, že exponenciální funkce generování splňuje diferenciální rovnice ${ displaystyle B '(x) = e ^ {x} B (x)}$. Samotnou funkci lze najít řešením této rovnice.^[9][10][11]

Okamžiky rozdělení pravděpodobnosti

Čísla Bellů uspokojí Dobinského vzorec^[12][9][11]

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

Tento vzorec lze odvodit rozšířením funkce exponenciálního generování pomocí Taylor série pro exponenciální funkci a poté sbírat termíny se stejným exponentem.^[8]To umožňuje B_n má být vykládáno jako nth okamžik a Poissonovo rozdělení s očekávaná hodnota 1.

The nČíslo Bell je také součtem koeficientů v nth kompletní Bellův polynom, který vyjadřuje nth okamžik ze všech rozdělení pravděpodobnosti jako funkce prvního n kumulanty.

Modulární aritmetika

Čísla Bellů poslouchají Touchardova shoda: Pokud str je jakýkoli prvočíslo pak^[13]

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

nebo zobecňující^[14]

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

Kvůli Touchardově shodě jsou čísla Bell periodická modulo str, pro každé prvočíslo str; například pro str = 2, čísla Bell opakují vzorec lichý-lichý-sudý s periodou tři. Období tohoto opakování pro libovolné prvočíslo str, musí být dělitelem

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

a pro všechny hlavní str ≤ 101 a str = 113, 163, 167 nebo 173, je to přesně toto číslo (sekvence A001039 v OEIS ).^[15][16]

Období čísel Bell na modulo n jsou

1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, 25239592216021, 411771, 10153, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784341, 85593501183 9431773737 75718776648063, 117, 1647084, 91703076898614683377208150526107718802981, 30459, 568972471024107865287021434301977158534824481, 96, 370905171793, 155107549103688143283, 107197717, 156 A054767 v OEIS )

Integrální zastoupení

Aplikace Cauchyho integrální vzorec exponenciální generující funkci získá komplexní integrální reprezentaci

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

Některé asymptotické reprezentace lze poté odvodit standardní aplikací metoda nejstrmějšího klesání.^[17]

Konkávnost

Čísla Bell tvoří a logaritmicky konvexní sekvence. Rozdělíme je podle faktoriálů, B_n/n!, dává logaritmicky konkávní sekvenci.^[18][19][20]

Tempo růstu

Několik asymptotické vzorce pro čísla Bell jsou známé. v Berend & Tassa (2010) byly stanoveny následující hranice:

${ displaystyle B_ {n} < left ({ frac {0,792n} { ln (n + 1)}} right) ^ {n}}$ pro všechna kladná celá čísla ${ displaystyle n}$;

navíc, pokud ${ displaystyle varepsilon> 0}$ pak pro všechny ${ displaystyle n> n_ {0} ( varepsilon)}$,

${ displaystyle B_ {n} < left ({ frac {e ^ {- 0,6+ varepsilon} n} { ln (n + 1)}} right) ^ {n}}$

kde ${ displaystyle ~ n_ {0} ( varepsilon) = max left {e ^ {4}, d ^ {- 1} ( varepsilon) right } ~}$ a${ displaystyle ~ d (x): = ln ln (x + 1) - ln ln x + { frac {1 + e ^ {- 1}} { ln x}} ,.}$Čísla zvonů lze také aproximovat pomocí Funkce Lambert W., funkce se stejnou rychlostí růstu jako logaritmus, jako ^[21]

${ displaystyle B_ {n} sim { frac {1} { sqrt {n}}} vlevo ({ frac {n} {W (n)}} vpravo) ^ {n + { frac {1 } {2}}} exp left ({ frac {n} {W (n)}} - n-1 right).}$

Moser & Wyman (1955) založil expanzi

${ displaystyle B_ {n + h} = { frac {(n + h)!} {W (n) ^ {n + h}}} krát { frac { exp (e ^ {W (n) } -1)} {(2 pi B) ^ {1/2}}} times left (1 + { frac {P_ {0} + hP_ {1} + h ^ {2} P_ {2} } {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)}) vpravo)}$

jednotně pro ${ displaystyle h = O ( ln (n))}$ tak jako ${ displaystyle n rightarrow infty}$, kde ${ displaystyle B}$ a každý ${ displaystyle P_ {i}}$ a ${ displaystyle Q_ {i}}$ jsou známé výrazy v ${ displaystyle W (n)}$.^[22]

Asymptotický výraz

${ displaystyle { begin {zarovnáno} { 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 na infty end {zarovnáno}}}$

byla založena de Bruijn (1981).

Bell připraví

Gardner (1978) nastolila otázku, zda je také nekonečně mnoho Bellů prvočísla. Prvních několik čísel Bell, která jsou prvočísla, jsou:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (sekvence A051131 v OEIS )

odpovídající indexům 2, 3, 7, 13, 42 a 55 (sekvence A051130 v OEIS ).

Další Bell Prime je B₂₈₄₁, což je přibližně 9,30740105 × 10⁶⁵³⁸.^[23] Od roku 2018^{[Aktualizace]}, je to největší známé primární číslo Bell. Phil Carmody ukázal, že to byl pravděpodobný prime v roce 2002. Po 17 měsících výpočtu s Marcelem Martinem ECPP program Primo, Ignacio Larrosa Cañestro se ukázal jako hlavní v roce 2004. Níže vyloučil další možná prvočísla B₆₀₀₀, později rozšířena na B₃₀₄₄₇ podle Eric Weisstein.^[24]

Dějiny

Čísla Bell jsou pojmenována po Eric Temple Bell, který o nich psal v roce 1938 v návaznosti na dokument z roku 1934, ve kterém studoval Polynomy zvonu.^[25][26] Bell netvrdil, že tato čísla objevil; ve svém příspěvku z roku 1938 napsal, že Bellova čísla „byla často vyšetřována“ a „byla znovuobjevena mnohokrát“. Bell cituje několik dřívějších publikací o těchto číslech, počínaje Dobiński (1877) který dává Dobińského vzorec pro čísla Bell. Bell nazval tato čísla „exponenciálními čísly“; název „Bell Bell“ a zápis B_n neboť tato čísla jim byla dána Becker a Riordan (1948).^[27]

Zdá se, že první vyčerpávající výčet nastavených oddílů nastal ve středověkém Japonsku, kde (inspirovaný popularitou knihy Příběh Genji ) společenská hra s názvem genji-ko vyskočil, ve kterém hosté dostali pět balíčků kadidla na vůni a byli požádáni, aby uhodli, které jsou stejné jako ostatní a které se liší. 52 možných řešení počítaných podle čísla Bell B₅, bylo zaznamenáno 52 různými diagramy, které byly vytištěny nad nadpisy kapitol v některých vydáních The Tale of Genji.^[28][29]

v Srinivasa Ramanujan Druhý zápisník zkoumal Bellovy polynomy i Bellova čísla.^[30]Časné reference pro Bell trojúhelník, který má čísla Bell na obou stranách, patří Peirce (1880) a Aitken (1933).

Viz také

• Dotykové polynomy
• Katalánské číslo

Poznámky

Reference

externí odkazy

• Robert Dickau. „Schémata čísel zvonů“.
• Weisstein, Eric W. „Číslo zvonu“. MathWorld.
• Gottfried Helms. "Další vlastnosti a zobecnění čísel zvonů" (PDF).