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₀ = 1 ja = B₁ = 1. Ensimmäiset Bellin luvut ovat

1, 1, 2, 5, 15, 52, 203, 877, 4140, ... A000110 OEIS-tietokannassa.

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 loppu­soinnussa keskenään.

Toisessa yhteydessä Bellin luvut esiintyvät myös toden­näköisyys­jakaumien momentteina. Erityisesti B_n on sen Poissonin jakauman n:s momentti, jonka odotusarvo on 1.

Joukon ositukset

Joukkojen ositukset voidaan järjestää osittaiseen järjestykseen, mikä osoittaa, että jokainen n-alkioisen joukon ositus käyttää hyväkseen jotakin n-1-alkioisen joukon ositusta.

5-alkioisen joukon 52 ositusta

Yleisesti B_n on n-alkioisen joukon ositusten lukumäärä. Joukon S ositus määritellään joukoksi ei-tyhjiä, toisistaan erillisiä S:n osajoukkoja, joiden unioni on S. Esimerkiksi B₃ = 5, koska kolmialkioinen joukko {a, b, c} voidaan osittaa viidellä eri tavalla:

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

{ {a}, {b, c} }

{ {b}, {a, c} }

{ {c}, {a, b} }

{ {a, b, c} }.

B₀ 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

Kolmiomainen taulukko, jonka kunkin rivin oikeassa laidassa olevat luvut ovat Bellin lukuja.

Bellin luvut voidaan helposti laskea muodostamalla niin sanottu Bellin kolmio. SItä sanotaan myös Aitkenin taulukoksi tai Peircen kolmioksi Alexander Aitkenin ja Charles Sandersin mukaan.

Kolmio muodostetaan seuraavasti:

1. Aloitetaan luvusta 1. Se yksinään muodostaa kolmion ylimmän (nollannen) rivin.($x_{0,1}=1$)
2. Aloitetaan uusi rivi siten, että edellisen rivin viimeinen luku kopioidaan uuden rivin ensimmäiseksi luvuksi. ($x_{i,1}\leftarrow x_{i-1,r}$, missä r on (i-1):nnen rivin viimeinen luku)
3. 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: $(x_{i,j}\leftarrow x_{i,j-1}+x_{i-1,j-1})$
4. Kohta 3 toistetaan, kunnes rivillä on yksi luku enemmän kuin edellisellä rivillä (eli kunnes $j=r+1$)
5. Tämän jälkeen aloitetaan jälleen uusi rivi kopioimalla edellisen rivin viimeinen luku uuden rivin ensimmäiseksi.
6. Kunkin rivin ensimmäinen luku on tämän rivin Bellin luku. ($B_{i}\leftarrow x_{i,1}$)

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_n 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 B₅=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/

Aiheesta muualla

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