Stirling-szám
![]() | Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját! |
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
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
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
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
Az Lah-számokat néha harmadfajú Stirling-számnak is hívják.[2]
Fordítottsági kapcsolat
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
Abramowitz és Stegun megad egy szimmetrikus összefüggést az első- és másodfajú Strirling-számokra:
és
Jegyzetek
- ↑ Aigner, Martin. Section 1.2 - Subsets and Binomial Coefficients, A Course In Enumeration. Springer, 561. o. (2007). ISBN 3-540-39032-4
- ↑ https://books.google.hu/books?id=B2WZkvmFKk8C&pg=PA464&lpg=PA464&dq=%22Stirling+numbers+of+the+third+kind%22&source=bl&ots=JhIJKIhaFH&sig=_0-CWfixhUoAuhh7DAo4fJco6y4&hl=en&ei=BKh2TfnBJ_KH0QGn17XZBg&sa=X&oi=book_result&ct=result&redir_esc=y#v=onepage&q=%22Stirling%20numbers%20of%20the%20third%20kind%22&f=false
Források
- 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
- Kombinatorika
- Numerikus sorok
- Permutáció
![]() | Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |