Stirling-szám

A Wikipédiából, a szabad enciklopédiából

A matematikában a Stirling-számok számos területen fordulnak elő analízisbeli és kombinatorikai problémáknál. A James Stirling (1692–1770) skót matematikusról elnevezett Stirling-számoknak két fajtája különböztethető meg:

  • Elsőfajú Stirling-számok
  • Másodfajú Stirling-számok

Jelölés[szerkesztés]

A Stirling-számokra többféle jelölés is használatos. Az elsőfajú Stirling-számokat kis s, a másodfajú Stirling-számokat nagy S betű jelöli. Az elsőfajú Stirling-számok negatívak is lehetnek, a másodfajú Stirling-számok csak pozitív számok lehetnek. Az általános jelölés:

Elsőfajú Stirling-számokra:

Másodfajú Stirling-számokra:

Milton Abramowitz és Irene Stegun nagybetűket és gót betűket használ, Jovan Karamata 1935-ben vezette be a szögletes és kapcsos zárójeles jelölést.

Elsőfajú Stirling-számok[szerkesztés]

A következő képletben a Stirling-szám az együttható

ahol (a Pochhammer-szimbólum) a csökkenő faktoriálist jelöli,

Megjegyzés: (x)0 = 1, mert ez egy üres szorzat. A kombinatorikában gyakran használják az jelölést a csökkenő faktoriálisra és az jelölést a növekvő faktoriálisra.[1] Az elsőfajú Stirling-szám abszolút értéke n elem permutációinak számát adja k diszjunkt ciklus esetén. Az alábbi táblázat az első néhány elsőfajú Stirling-számot mutatja:

ahol:

Másodfajú Stirling-számok[szerkesztés]

Definíció: Az másodfajú Stirling-szám egy n elemű halmaz k osztályú osztályozásainak a száma. Rögzített n mellett az összegük az n-edik Bell-szám:

A másodfajú Stirling-számokra vonatkozó rekurzió:

Bizonyítás: A definíció szerint ez az (n+1) elemű halmaz az összes k-részre való partícióinak (osztályfelbontásának) számát jelenti. Egy ilyen partíciónak a halmaz (n+1)-edik elemét tartalmazó blokkja (halmaza) vagy egyelemű, vagy egynél több elemű. Ha ez a blokk egyelemű, akkor összesen ilyen eset van (a maradék n elemet a maradék (k-1) részhalmazra kell partícionálnunk, majd a partícióhoz hozzávesszük az (n+1)-edik elemet tartalmazó egyelemű halmazt). Ha a blokk egynél több elemű, akkor összesen ilyen eset van (a maradék n elemet k részhalmazra kell partícionálnunk, majd az egyik részhalmazhoz hozzávesszük az (n+1)-edik elemet, ezt k féleképpen tehetjük meg).

Másodfajú Stirling-számok képlete:

Bizonyítás: Legyen , és legyen egy szürjektív függvény, illetve , ekkor az halmaz egy k osztályú partíciója. Ha összesen ilyen függvény van, akkor k osztályú partíciója van az halmaznak, mivel halmazokat permutálva a partíció ugyanaz marad, de megváltozik. A Szitaformula alapján megmutatható, hogy a szürjektív függvények száma .

A másodfajú Stirling-számok és a csökkenő faktoriális kapcsolata:

ahol (Pochhammer-szimbólum) a csökkenő faktoriálist jelöli:

Bizonyítás: Legyen és , illetve , ekkor összesen darab függvény létezik. Legyen képhalmaza , ekkor függvény szürjektív. halmazra fennáll, hogy . Ha , ahol , ( ), akkor ilyen függvény van, ezt a k elemet -ből féleképpen választhatjuk ki, vagyis összesen darab függvény van, melyre . Mivel , ezért darab függvény létezik. Az egyenlőség két oldalán n-edfokú polinom áll és a tételt minden természetes számra bizonyítottuk, ezért a tétel minden valós x-re igaz.

Lah-számok[szerkesztés]

Az Lah-számokat néha harmadfajú Stirling-számnak is hívják.[2]

Fordítottsági kapcsolat[szerkesztés]

Az első- és másodfajú Stirling-számok tekinthetők úgy is, mint egymás inverzei:

és

ahol a Kronecker-delta-függvény.

Szimmetrikusság[szerkesztés]

Abramowitz és Stegun megad egy szimmetrikus összefüggést az első- és másodfajú Strirling-számokra:

és

Jegyzetek[szerkesztés]

Források[szerkesztés]

  • Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Konkrét matematika, Műszaki Könyvkiadó, Budapest, 1998
  • Hsien-Kuei Hwang (1995). "Asymptotic Expansions for the Stirling Numbers of the First Kind". Journal of Combinatorial Theory, Series A 71 (2): 343–351. doi:10.1016/0097-3165(95)90010-1

Kapcsolódó szócikkek[szerkesztés]