Bellovo število

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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 (B0, B1) sta enaki 1, druga pa tvorijo celoštevilsko zaporedje (OEIS A000110):

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

Particije množice[uredi | uredi kodo]

V splošnem je Bn š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 B3 = 5, saj lahko množico s tremi elementi {abc} razdelimo na 5 različnih načinov:

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

B0 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}}. B2 = 2, saj lahko dano množico z dvema elementoma {ab} razdelimo na dva različna načina:

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

Druga opredelitev Bellovih števil[uredi | uredi kodo]

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.

Značilnosti Bellovih števil[uredi | uredi kodo]

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}.

Asimptotična meja[uredi | uredi kodo]

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  \lambda(n) = e^{\operatorname{W}(n)}, kjer je W Lambertova funkcija W. (Lovász, 1993)

Bellova praštevila[uredi | uredi kodo]

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 B2841, ki je približno 9,30740105 · 106538. [1] Trenutno je največje znano Bellovo praš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 B6000, kar je Eric Wolfgang Weisstein kasneje razširil na B30447.

Zunanje povezave[uredi | uredi kodo]