|
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
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:
![{\displaystyle s(n,k)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4e05fa2e535d3ba251305da934078f5817ed293)
Elsőfajú Stirling-számokra:
![{\displaystyle c(n,k)=\left[{n \atop k}\right]=|s(n,k)|\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9188fec1ae1f48766e21f459f3d31cad3eb42474)
Másodfajú Stirling-számokra:
![{\displaystyle S(n,k)=\left\{{n \atop k}\right\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91796affa451aea043d205f659e8185a361de322)
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,
![{\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e468f33ab351359893976b178b62367c20e7b86)
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:
![{\displaystyle {\begin{array}{ccccccccccc}&&&&&~~1~~&&&&&\\&&&&-1&&~~1~~&&&&\\&&&2&&-3&&~~1~~&&&\\&&-6&&11&&-6&&~~1~~&&\\&24&&-50&&35&&-10&&~~1~~&\\-120&&274&&-225&&85&&-15&&~~1~~\\\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63f0112839cbd57db1bf5f3439a553eaef3622de)
ahol:
![{\displaystyle s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95e577f0e133de2118d74f7541714195b8d6391b)
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.
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:
![{\displaystyle \sum _{j=0}^{n}s(n,j)S(j,k)=\delta _{nk}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62bb8e32980a15c6a42850e6f7229aad35d7bfa9)
és
![{\displaystyle \sum _{j=0}^{n}S(n,j)s(j,k)=\delta _{nk},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7201411803d682bf1548e5fe5a948fdf7823a1c)
ahol
a Kronecker-delta-függvény.
Abramowitz és Stegun megad egy szimmetrikus összefüggést az első- és másodfajú Strirling-számokra:
![{\displaystyle s(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}S(n-k+j,j)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f139f214e5213623a04fba209d70e4a6301e1533)
és
![{\displaystyle S(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}s(n-k+j,j).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c8e64070d244817abb18b3451f8dc6696765aea)
- 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