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 B_n-nel jelölt n-edik Bell-szám egyúttal egy n elemű halmaz ekvivalenciarelációinak száma. Például B₃ = 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, … (A000110 sorozat az OEIS-ben)

Összefüggések

A Bell-számokat a másodfajú Stirling-számok összegzésével kapjuk:

${\displaystyle B_{n}=\sum _{k=0}^{n}S(n,k).}$

A Bell-számokra vonatkozó rekurzív képlet:

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{{n \choose k}B_{k}}.}$

Érvényes továbbá a következő formula:

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}\,}$ (Dobiński 1877)^[1]

A Bell-számok aszimptotikus nagyságrendje:

${\displaystyle B_{n}\sim {\frac {1}{\sqrt {n}}}\lambda _{n}^{n+{\frac {1}{2}}}e^{\lambda _{n}-n-1},}$ ahol ${\displaystyle \lambda _{n}\ln \lambda _{n}=n.}$

A Bell-számok sorozatának exponenciális generátorfüggvénye:

${\displaystyle \sum _{n=0}^{\infty }B_{n}{\frac {x^{n}}{n!}}=\exp(\exp(x)-1).}$

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.

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

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

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!