Bell-szám

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 {abc} 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, … (A000110 sorozat az OEIS-ben)

Ö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)[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

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[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.

Bell háromszög készítése
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

  1. Az első sorban egy egyes van.
  2. Vesszük a következő sort. (n növelése 1-gyel)
  3. Az n. sor 1. eleme egyenlő az n-1. sor utolsó elemével.
  4. 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.
  5. Vissza a 2. lépésre.

Jegyzetek

  1. G. Dobiński: Summirung der Reihe für m = 1, 2, 3, 4, 5, …, Grunert-Archiv 61, 1877, S. 333–336
  2. "Sloane's A011971 : Aitken's array", On-Line Encyclopedia of Integer Sequences, OEIS Foundation

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