Bellin luvut

**Bellin luvut** osoittavat kombinatoriikassa, kuinka monella tavalla äärellinen joukko voidaan osittaa. 

Bellin lukuja matemaatikot ovat tutkineet 1800-luvulta lähtien, mutta jo sitä ennen ne tunnettiin keskiajan Japanissa. Nimensä ne kuitenkin ovat saaneet Eric Temple Bellin mukaan, joka tutki niitä 1930-luvulla – hyvä esimerkki Stiglerin laista, jonka mukaan keksintöjä ei koskaan nimetä alkuperäisen keksijänsä mukaan.

Bellin numeroille käytetään merkintää *B**n*, missä *n* on kokonaisluku, vähintään nolla. Bellin lukujen jono alkaa luvuilla *B*0 = 1 ja *B*1 = 1. Ensimmäiset Bellin luvut ovat 
:1, 1, 2, 5, 15, 52, 203, 877, 4140, ... .
Bellin luku *B**n* osoittaa, kuinka monella tavalla *n*-alkioinen joukko voidaan osittaa, tai yhtä­pitävästi, kuinka monta ekvivalenssirelaatiota siinä voidaan määritellä.  Luku *B*n* osoittaa myös, kuinka monella tavalla *n*-säkeisen runon säkeet voidaan ryhmitellä siten, että samaan ryhmään kuuluvat säkeet ovat [[loppusointu|loppu­soinnussa]] keskenään.

Toisessa yhteydessä Bellin luvut esiintyvät myös [[todennäköisyysjakauma|toden­näköisyys­jakaumien]] [[momentti (tilastotiede)|momentteina]]. Erityisesti *Bn* on sen [[Poissonin jakauma]]n *n*:s momentti, jonka [[odotusarvo]] on 1.

== Kaavoja ==
Bellin lukujen laskemiseen on muodostettu erilaisia kaavoja:

* <math>B_n = \sum_{k=0}^{n-1} B_k \binom{n-1}{k}  </math>
* <math>B_n = \lceil e^{-1} \sum_{m=1}^{2n} \frac{m^n}{m!} \rceil  </math>
* <math>B_n = \frac{1}{e} \sum_{k=0}^{\infin} \frac{k^n}{k!}  </math>

==Joukon ositukset ==


Yleisesti *B*<sub>*n*</sub> on *n*-alkioisen joukon [[ositus]]ten lukumäärä. Joukon *S* ositus määritellään joukoksi ei-tyhjiä, toisistaan erillisiä *S*:n osajoukkoja, joiden unioni on *S*. Esimerkiksi *B*<sub>3</sub>&nbsp;=&nbsp;5, koska kolmialkioinen joukko {*a*,&nbsp;*b*,&nbsp;*c*} voidaan osittaa viidellä eri tavalla:

:{ {*a*}, {*b*}, {*c*} }
:{ {*a*}, {*b*, *c*} }
:{ {*b*}, {*a*, *c*} }
:{ {*c*}, {*a*, *b*} }
:{ {*a*, *b*, *c*} }.

*B*<sub>0</sub> on 1, koska [[tyhjä joukko]] voidaan osittaa vain yhdellä tavalla. Kuten edellä oleva merkintä osoittaa, osituksessa ei ole merkitystä sillä, missä järjestyksessä osajoukot luetellaan eikä sillä, missä järjestyksessä kunkin osajoukin alkiot luetellaan. Toisin sanoen seuraavat ositukset käsitetään samaksi:
:{ {*b*}, {*a*, *c*} }
:{ {*a*, *c*}, {*b*} }
:{ {*b*}, {*c*, *a*} }
:{ {*c*, *a*}, {*b*} }.

== Bellin kolmio ==


Bellin luvut voidaan helposti laskea muodostamalla niin sanottu *'Bellin kolmio**. SItä sanotaan myös **Aitkenin taulukoksi** tai **Peircen kolmioksi*' [[Alexander Aitken]]in ja [[Charles Sanders]]in mukaan.

Kolmio muodostetaan seuraavasti:
# Aloitetaan luvusta 1. Se yksinään muodostaa kolmion ylimmän (nollannen) rivin.(<math> x_{0,1} = 1 </math>)
# Aloitetaan uusi rivi siten, että edellisen rivin viimeinen luku kopioidaan uuden rivin ensimmäiseksi luvuksi. (<math>x_{i,1} \leftarrow x_{i-1, r}</math>, missä *r* on (*i*-1):nnen rivin viimeinen luku)
# Luvut, jotka eivät ole rivin ensimmäisenä, muodostetaan laskemalla yhteen edellisessä sarakkeessa samalla ja edellisellä rivillä olevat luvut, toisin sanoen välittömästi luvun vasemmalla puolella oleva sekä yläviistossa vasemmalla puolella oleva luku:  <math>( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )</math> 
# Kohta 3 toistetaan, kunnes rivillä on yksi luku enemmän kuin edellisellä rivillä (eli kunnes <math> j = r + 1 </math>)
# Tämän jälkeen aloitetaan jälleen uusi rivi kopioimalla edellisen rivin viimeinen luku uuden rivin ensimmäiseksi.
# Kunkin rivin ensimmäinen luku on tämän rivin *Bellin luku*. (<math>B_i \leftarrow x_{i,1}</math>)

Seuraavassa ovat seitsemän ensimmäistä tällä tavoin konstruoitua riviä:

   1
   1   2
   2   3   5
   5   7  10  15
  15  20  27  37  52
  52  67  87 114 151 203
 203 255 322 409 523 674 877

Bellin luvut ovat sekä kolmion vasemmassa että oikeassa laidassa. Jokainen luku *B*<sub>*n*</sub> on sekä *n*:nnen rivin alussa että *n*-1:nnen rivin lopussa (kun kolmion ylälaidassa oleva rivi, jossa on vain luku 1, lasketaan nollanneksi riviksi). Esimerkiksi luku *B5''=52 on sekä neljännen rivin lopussa että viidennen rivin alussa.

## Lähteet
* https://www.geeksforgeeks.org/bell-numbers-number-of-ways-to-partition-a-set/

### Viitteet

## Aiheesta muualla
*Tytti Järvinen: Joukkojen osituksesta, Helsingin yliopisto, Matematiikan ja tilastotieteen laitos, Pro gradu -tutkielma, Maaliskuu 2016 (pdf)