thumb|5 objektum összes lehetséges (52) osztályozása
A kombinatorikában az Eric Temple Bellről elnevezett n-edik Bell-szám egy n elemű halmaz lehetséges osztályozásainak száma. A Bn-nel jelölt n-edik Bell-szám egyúttal egy n elemű halmaz ekvivalenciarelációinak száma. Például B3 = 5, mert az {a, b, c} háromelemű halmaznak 5 osztályozása van:
{ {a}, {b}, {c} } { {a}, {b, c} } { {b}, {a, c} } { {c}, {a, b} } { {a, b, c} }
Bell-számok
A sorozat első elemei a nulladik tagtól kezdődően:
1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, …
Összefüggések
A Bell-számokat a másodfajú Stirling-számok összegzésével kapjuk:
A Bell-számokra vonatkozó rekurzív képlet:
Érvényes továbbá a következő formula:
(Dobiński 1877)G. Dobiński: Summirung der Reihe für m = 1, 2, 3, 4, 5, …, Grunert-Archiv 61, 1877, S. 333–336
A Bell-számok aszimptotikus nagyságrendje:
ahol
A Bell-számok sorozatának exponenciális generátorfüggvénye:
Bell-háromszög
A Bell-háromszög a Pascal-háromszöghöz hasonló elrendezésű ábra, amely a Bell-számok egyszerű kiszámolását adja. Egyéb elnevezései Aitken-sorozat vagy Peirce-háromszög Alexander Aitken és Charles Sanders Peirce"Sloane's A011971 : Aitken's array", On-Line Encyclopedia of Integer Sequences, OEIS Foundation után. Jelen esetben a bal szélső sor tartalmazza a Bell-számokat, a jobb szélső eggyel előrébb jár.
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
Bell-háromszög rajzolásának lépései Az első sorban egy egyes van. Vesszük a következő sort. (n növelése 1-gyel) Az n. sor 1. eleme egyenlő az n-1. sor utolsó elemével. Az n. sor minden elemére (m=2,...,n): Az n. sor m. eleme egyenlő az n. sor m-1. és az n-1. sor m-1. elemének összegével. Vissza a 2. lépésre.
Jegyzetek
Források Hajnal Péter: Összeszámlálási problémák, Polygon jegyzettár, Szeged Katona Gyula Y., Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex, Budapest Lovász László: Kombinatorikai problémák és feladatok, Typotex, Budapest
Kategória:Nevezetes számsorozatok