Bellovo število

Iz Wikipedije, proste enciklopedije

Bellova števila (tudi eksponentna števila) so v matematiki in kombinatoriki števila particij množic z n elementi, oziroma so števila ekvivalenčnih relacij na njih. Imenujejo se po Ericu Templeu Bellu. Prvi dve Bellovi števili (B₀, B₁) sta enaki 1, druga pa tvorijo celoštevilsko zaporedje (OEIS A000110):

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

[uredi] Particije množice

V splošnem je B_n število particij množice z n elementi. Particija množice S je določena kot neprazne, paroma razdeljene podmnožice S, katerih unija je S. Na primer B₃ = 5, saj lahko množico s tremi elementi {a, b, c} razdelimo na 5 različnih načinov:

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

{{a}, {b, c}}

{{b}, {a, c}}

{{c}, {a, b}}

B₀ je 1, ker obstaja natanko ena particija prazne množice. Vsak element prazne množice je neprazna množica, kar je trivialno resnično, in njihova unija je prazna množica. Zaradi tega je prazna množica edina particija same sebe.

Vrstni red particij ali elementov pri tem nista pomembna. Tako so naslednje particije istovetne:

{{b}, {a, c}}

{{a, c}, {b}}

{{b}, {c, a}}

{{c, a}, {b}}

Podobno je pri množici z enim elementom {a}. Razdelimo jo lahko na en način {{a}}. B₂ = 2, saj lahko dano množico z dvema elementoma {a, b} razdelimo na dva različna načina:

{{a}, {b}}

[uredi] Druga opredelitev Bellovih števil

Bellova števila so tudi števila različnih možnih postavitev n razločljivih krogel v eno ali več nerazločljivih škatel. Naj je na primer n enak 3. Imamo tri krogle, ki jih označimo z a, b in c, ter tri škatle. Če škatel med seboj ne moremo razločevati, lahko vanje postavimo krogle na pet različnih načinov:

vsako kroglo damo v svojo škatlo.
vse tri krogle damo v eno škatlo. Ker so škatle med seboj istovetne, je to edina možna kombinacija razporeditev krogel.
kroglo a damo v eno škatlo; krogli b in c damo v drugo škatlo.
kroglo b damo v eno škatlo; krogli a in c damo v drugo škatlo.
kroglo c damo v eno škatlo; krogli a in b damo v drugo škatlo.

[uredi] Lastnosti Bellovih števil

Za Bellova števila velja rekurenčna enačba:

$B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k} = \sum_{k=1}^{n+1} {n \choose k-1} B_{n+1-k} .$

Za Bellova števila velja enačba (G. Dobinsky):

$B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}=$ n-ti moment Poissonove porazdelitve z matematičnim upanjem 1.

Za Bellova števila velja »Touchardova kongruenca«: če je p poljubno praštevilo, velja:

$B_{p+n}\equiv B_n+B_{n+1}\ (\operatorname{mod}\ p).$

Vsako Bellovo število je vsota »Stirlingovih števil druge vrste«

$B_n=\sum_{k=1}^n S(n,k).$

Stirlingovo število S(n, k) je število načinov particij množice s kardinalnostjo n v natanko k nepraznih podmnožic.

n-to Bellovo število je tudi vsota koeficientov v polinomu, ki izraža n-ti moment vsake verjetnostne porazdelitve kot funkcijo prvih n kumulant. Ta način številčenja particij ni tako preprost kot številčenje s Stirlingovimi števili.

Eksponenta rodovna funkcija za Bellova števila je:

$\sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.$

[uredi] Asimptotična meja

Asimptotična enačba za Bellova števila je:

$B_n \sim \frac{1}{{\sqrt n }}\left[ {\lambda \left( n \right)} \right]^{n + \frac{1}{2}} e^{\lambda \left( n \right) - n - 1}.$

Tukaj je $λ(n) = e W (n),$ kjer je W Lambertova funkcija W. (Lovász, 1993)

[uredi] Praštevilska Bellova števila

Prva Bellova števila, ki so tudi praštevila so:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837

z indeksi Bellovih števil 2, 3, 7, 13, 42 in 55 (OEIS A051130)

Naslednje praštevilo je B₂₈₄₁, ki je približno 9,30740105 · 10⁶⁵³⁸. [1] Trenutno je največje znano praštevilsko Bellovo število. Phil Carmody je leta 2002 pokazal, da je verjetno praštevilo. Po 17. mesecih računanja s programom Primo Marcela Martina, je Ignacio Larrosa Cañestro leta 2004 pokazal, da je praštevilo. Izključil je vsa druga možna praštevila manjša od B₆₀₀₀, kar je Eric Weisstein kasneje razširil na B₃₀₄₄₇.

Vzpostavljeno iz »http://sl.wikipedia.org../../../b/e/l/Bellovo_%C5%A1tevilo.html«

Kategorija: Zaporedja