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ää Bn, missä n on kokonaisluku, vähintään nolla. Bellin lukujen jono alkaa luvuilla B0 = 1 ja = B1 = 1. Ensimmäiset Bellin luvut ovat
- 1, 1, 2, 5, 15, 52, 203, 877, 4140, ... A000110 OEIS-tietokannassa.
Bellin luku Bn osoittaa, kuinka monella tavalla n-alkioinen joukko voidaan osittaa, tai yhtäpitävästi, kuinka monta ekvivalenssirelaatiota siinä voidaan määritellä. Luku Bn osoittaa myös, kuinka monella tavalla n-säkeisen runon säkeet voidaan ryhmitellä siten, että samaan ryhmään kuuluvat säkeet ovat loppusoinnussa keskenään.[1]
Toisessa yhteydessä Bellin luvut esiintyvät myös todennäköisyysjakaumien momentteina. Erityisesti Bn on sen Poissonin jakauman n:s momentti, jonka odotusarvo on 1.
Joukon ositukset
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f6/Bell_numbers_subset_partial_order.svg/250px-Bell_numbers_subset_partial_order.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/19/Set_partitions_5%3B_circles.svg/250px-Set_partitions_5%3B_circles.svg.png)
Yleisesti Bn 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 B3 = 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} }.
B0 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
![](http://upload.wikimedia.org/wikipedia/commons/a/ab/BellNumberAnimated.gif)
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.[2]
Kolmio muodostetaan seuraavasti:
- Aloitetaan luvusta 1. Se yksinään muodostaa kolmion ylimmän (nollannen) rivin.()
- Aloitetaan uusi rivi siten, että edellisen rivin viimeinen luku kopioidaan uuden rivin ensimmäiseksi luvuksi. (, 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:
- Kohta 3 toistetaan, kunnes rivillä on yksi luku enemmän kuin edellisellä rivillä (eli kunnes )
- 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. ()
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 Bn 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)