Kuinka monta eri ekvivalenssiluokitusta n alkioisella joukolla A voi olla? Eli kuinka monella eri tavalla n alkioinen joukko A voidaan jakaa sellaisiin erillisiin epätyhjiin osajoukkoihin A_i, että unioni A_i = A?
Ekvivalenssiluokkia
muumisetä
4291
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 4
Vanhimmat
Kyseessä ovat ns. Bellin luvut. Katso esim. http://mathworld.wolfram.com/BellNumber.html. Tuon sivun kaavoilla voit laskea ositusten lukumääriä.
Kiitos vastauksesta.
Tarkoitus oli herättää keskustelua siitä miten tulos johdetaan. (olen nyt polleana kun sain laskettua tapauksen kun n = 5 kynällä ja paperilla ilman Belliä tai kumppaneita :) Matkalla tuli (näköjään) vastaan myös toisen luokan Stirlingin luvut.
Onko ideoita miten yleistä tapausta voisi lähteä johtamaan? Osaan yhden tavan ja jos jollain on mahdollisesti erilainen lähestymistapa, niin olisi mielenkiintoista kuulla.
Rekursiokaavan todistaminen ei ole vaikeaa, ja se löytyy esimerkiksi osoitteesta http://planetmath.org/encyclopedia/BellNumber.html. Generoivan funktion kaavan todistus löytyy taas täältä: http://ndp.jct.ac.il/tutorials/Discrete/node101.html
Todistukset ovat tuttuja (tulivat tutuiksi), mutta hainkin kaavan johtamista eri menetelmillä.