Bell-szám
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
szerkesztésA sorozat első elemei a nulladik tagtól kezdődően:
Összefüggések
szerkesztésA 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)[1]
A Bell-számok aszimptotikus nagyságrendje:
- ahol
A Bell-számok sorozatának exponenciális generátorfüggvénye:
Bell-háromszög
szerkesztésA 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[2] 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
szerkesztés- 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
szerkesztés- ↑ G. Dobiński: Summirung der Reihe für m = 1, 2, 3, 4, 5, …, Grunert-Archiv 61, 1877, S. 333–336
- ↑ "Sloane's A011971 : Aitken's array", On-Line Encyclopedia of Integer Sequences, OEIS Foundation
Források
szerkesztés- 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