A Stirling-számok és a golyók dobozokba rendezése

Mi is az a Stirling-szám?

A Stirling-számok (elsőfajú és másodfajú Stirling-számok is léteznek, de most a másodfajú Stirling-számokról beszélünk) azt fejezik ki, hogy hányféleképpen lehet \(n\) különböző elemet \(k\) nem üres részhalmazra felosztani. Ebben az esetben a mi elemeink a golyók, a részhalmazok pedig a dobozok, amelyekbe a golyókat tesszük.

A Stirling-számok tehát megadják, hogy hányféleképpen lehet az \(n\) különböző golyót elhelyezni \(k\) olyan dobozba, hogy egyik doboz se maradjon üresen.

Példa: 3 golyó és 2 doboz

Vegyünk egy egyszerű példát: van \(3\) különböző golyónk (mondjuk piros, kék, és zöld), és ezeket szeretnénk \(2\) dobozba elhelyezni úgy, hogy mindkét dobozban legyen legalább egy golyó.

Nézzük meg, milyen lehetőségeink vannak:
1. Az egyik dobozban két golyó lehet, a másikban pedig egy.

Elrendezések:
– Az első dobozban a piros és a kék golyó, a másikban a zöld.
– Az első dobozban a piros és a zöld golyó, a másikban a kék.
– Az első dobozban a kék és a zöld golyó, a másikban a piros.

Ebben a konkrét esetben tehát összesen \(3\) különböző módon tudjuk a golyókat elosztani \(2\) doboz között úgy, hogy minden dobozban legyen legalább egy golyó. Ezt a számot a Stirling-számok adják meg, és ezt úgy írjuk le, hogy \( S(3, 2) = 3 \).

Általános megoldás Stirling-számokkal

Ha \(n\) golyót szeretnénk \(k\) nem üres dobozba helyezni, akkor a Stirling-szám \( S(n, k) \) megadja, hányféleképpen lehet ezt megtenni. Ezt a számot nem könnyű képlettel kifejezni, de vannak táblázatok és algoritmusok, amelyek segítenek ezeknek a számoknak a kiszámításában.

Például:
– \( S(4, 2) = 7 \): \(4\) különböző golyót \(2\) dobozba \(7\) különböző módon tudunk elhelyezni.
– \( S(5, 3) = 25 \): \(5\) különböző golyót \(3\) dobozba \(25\) különböző módon oszthatunk el.

Hogyan számoljuk ki a Stirling-számokat?

A Stirling-számok kiszámítása a következő rekurziós képleten alapul:

Ez azt jelenti, hogy egy adott Stirling-számot előző számok alapján számíthatunk ki. Az intuíció mögötte az, hogy az \(n\)-edik golyót vagy egy már létező dobozba tesszük (ami \(k\) féleképpen történhet), vagy egy új dobozt nyitunk neki (ami csak egyféleképpen lehetséges).

A Stirling-számok egy nagyon hasznos eszközt adnak a kezünkbe, ha különböző elemeket (például golyókat) egyforma dobozokba szeretnénk rendezni úgy, hogy egyik doboz se maradjon üres. Ezek a számok megmutatják, hányféle elrendezés létezik ilyen feltételek mellett. Legközelebb, amikor egy hasonló feladattal találkozol, gondolj a Stirling-számokra, mert ők adják meg a megoldást!