Пайдалану экспоненциалды генерациялау функциялары (EGF)Стирлинг сандары комбинаторлық математика және, мүмкін, оның канондық мысалы символикалық комбинаторика қолданылады. Сондай-ақ, олар осы екі типті сандардың құрылуындағы параллельдерді бейнелейді, олар үшін қолданылатын биномдық стильдегі жазбаға қолдау көрсетеді.
Бұл мақалада коэффициентті шығару операторы қолданылады [ з n ] { displaystyle [z ^ {n}]} ресми қуат сериялары , сондай-ақ (белгіленген) операторлар C { displaystyle { mathfrak {C}}} P { displaystyle { mathfrak {P}}} символикалық комбинаторика . Комбинаторлық класты ескере отырып, цикл операторы циклдік симметрияларды ескеретін бастапқы ұзындықтағы цикл бойымен объектілерді орналастыру арқылы алынған класты құрады, ал орнатылған оператор бастапқы класстан объектілерді орналастыру арқылы алынған класты жасайды жиынтық (симметриялы топтың симметриялары, яғни «құрылымсыз қап».) Екі комбинаторлық класс (қосымша маркерлерсіз көрсетілген)
ауыстыру (бірінші типтегі қол қойылмаған Stirling нөмірлері үшін): P = ОРНАТУ ( CYC ( З ) ) , { displaystyle { mathcal {P}} = operatorname {SET} ( operatorname {CYC} ({ mathcal {Z}})),} және
B = ОРНАТУ ( ОРНАТУ ≥ 1 ( З ) ) , { displaystyle { mathcal {B}} = оператордың аты {SET} ( оператордың аты {SET} _ { geq 1} ({ mathcal {Z}})),} қайда З { displaystyle { mathcal {Z}}}
Ескерту : Стерлинг нөмірлері үшін бұл жерде қолданылатын белгілер Уикипедиядағы Стерлинг нөмірлері туралы мақалаларға сәйкес келмейді; квадрат жақшалар бұл жерде қол қойылған Стирлинг сандарын білдіреді.
Стирлинг бірінші түрдегі нөмірлер
Бірінші типтегі қол қойылмаған Стирлинг нөмірлері [n ] бірге к циклдар. Ауыстыру - бұл циклдар жиынтығы, демек жиынтық P { displaystyle { mathcal {P}} ,}
P = ОРНАТУ ( U × CYC ( З ) ) , { displaystyle { mathcal {P}} = operatorname {SET} ({ mathcal {U}} times operatorname {CYC} ({ mathcal {Z}})), ,} синглтон қайда U { displaystyle { mathcal {U}}} кездейсоқ ауыстырудың статистикасы .
Функцияларды генерациялау арқылы бірінші типтегі қол қойылмаған Стирлинг сандарының аралас генерациялау функциясын аламыз:
G ( з , сен ) = эксп ( сен журнал 1 1 − з ) = ( 1 1 − з ) сен = ∑ n = 0 ∞ ∑ к = 0 n [ n к ] сен к з n n ! . { displaystyle G (z, u) = exp left (u log { frac {1} {1-z}} right) = left ({ frac {1} {1-z}} оңға) ^ {u} = sum _ {n = 0} ^ { infty} sum _ {k = 0} ^ {n} left [{ begin {matrix} n k end {matrix} } right] u ^ {k} , { frac {z ^ {n}} {n!}}.} Енді бірінші типтегі қол қойылған Стирлинг нөмірлері белгісіздерден қатынас арқылы алынады
( − 1 ) n − к [ n к ] . { displaystyle (-1) ^ {n-k} сол жақта [{ begin {matrix} n k end {matrix}} right].} Демек генераторлық функция H ( з , сен ) { displaystyle H (z, u)}
H ( з , сен ) = G ( − з , − сен ) = ( 1 1 + з ) − сен = ( 1 + з ) сен = ∑ n = 0 ∞ ∑ к = 0 n ( − 1 ) n − к [ n к ] сен к з n n ! . { displaystyle H (z, u) = G (-z, -u) = left ({ frac {1} {1 + z}} right) ^ {- u} = (1 + z) ^ { u} = sum _ {n = 0} ^ { infty} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k соңы {matrix}} right] u ^ {k} , { frac {z ^ {n}} {n!}}.} Мұны манипуляциялау арқылы әртүрлі сәйкестіліктер алынуы мүмкін генерациялық функция :
( 1 + з ) сен = ∑ n = 0 ∞ ( сен n ) з n = ∑ n = 0 ∞ з n n ! ∑ к = 0 n ( − 1 ) n − к [ n к ] сен к = ∑ к = 0 ∞ сен к ∑ n = к ∞ з n n ! ( − 1 ) n − к [ n к ] = e сен журнал ( 1 + з ) . { displaystyle (1 + z) ^ {u} = sum _ {n = 0} ^ { infty} {u select n} z ^ {n} = sum _ {n = 0} ^ { infty } { frac {z ^ {n}} {n!}} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k соңы {matrix}} right] u ^ {k} = sum _ {k = 0} ^ { infty} u ^ {k} sum _ {n = k} ^ { infty} { frac {z ^ {n}} {n!}} (- 1) ^ {nk} left [{ begin {matrix} n k end {matrix}} right] = e ^ {u log (1+) z)}.} Атап айтқанда, жинақтаудың тәртібі алмасуы мүмкін, және туындылар, содан кейін з немесе сен бекітілген болуы мүмкін.
Соңғы сомалар Қарапайым сома
∑ к = 0 n ( − 1 ) к [ n к ] = ( − 1 ) n n ! . { displaystyle sum _ {k = 0} ^ {n} (- 1) ^ {k} left [{ begin {matrix} n k end {matrix}} right] = (- 1) ^ {n} n !.} Бұл формула орындалады, өйткені қосындының экспоненциалды түзуші функциясы
H ( з , − 1 ) = 1 1 + з және демек n ! [ з n ] H ( з , − 1 ) = ( − 1 ) n n ! . { displaystyle H (z, -1) = { frac {1} {1 + z}} quad { mbox {және осыдан}} quad n! [z ^ {n}] H (z, -1) ) = (- 1) ^ {n} n !.} Шексіз сомалар Кейбір шексіз қосындыларға жатады
∑ n = к ∞ [ n к ] з n n ! = ( журнал ( 1 + з ) ) к к ! { displaystyle sum _ {n = k} ^ { infty} left [{ begin {matrix} n k end {matrix}} right] { frac {z ^ {n}} {n !}} = { frac { left ( log (1 + z) right) ^ {k}} {k!}}} қайда | з | < 1 { displaystyle | z | <1} з = 0 { displaystyle z = 0} журнал ( 1 + з ) { displaystyle log (1 + z)} з = − 1. { displaystyle z = -1.}
Бұл қатынас өйткені
[ сен к ] H ( з , сен ) = [ сен к ] эксп ( сен журнал ( 1 + з ) ) = ( журнал ( 1 + з ) ) к к ! . { displaystyle [u ^ {k}] H (z, u) = [u ^ {k}] exp left (u log (1 + z) right) = { frac { left ( log (1 + z) right) ^ {k}} {k!}}.} Стирлинг екінші түрдегі нөмірлер
Бұл сандар [бөлімдерінің санын есептейдіn ] ішіне к бос емес ішкі жиындар. Алдымен бөлімдердің жалпы санын қарастырыңыз, яғни. B n
B n = ∑ к = 1 n { n к } және B 0 = 1 , { displaystyle B_ {n} = sum _ {k = 1} ^ {n} left {{ begin {matrix} n k end {matrix}} right } { mbox {and} } B_ {0} = 1,} яғни Қоңырау нөмірлері . The Флажолет - Седжвиктің негізгі теоремасы қолданылады (белгіленген жағдай) .Жинағы B { displaystyle { mathcal {B}} ,}
B = ОРНАТУ ( ОРНАТУ ≥ 1 ( З ) ) . { displaystyle { mathcal {B}} = оператордың аты {SET} ( оператордың аты {SET} _ { geq 1} ({ mathcal {Z}})).} Бұл ыдырау жиынтықтың құрылысымен толығымен ұқсас P { displaystyle { mathcal {P}} ,}
P = ОРНАТУ ( CYC ( З ) ) . { displaystyle { mathcal {P}} = operatorname {SET} ( operatorname {CYC} ({ mathcal {Z}})).} және бірінші типтегі Стерлинг сандарын шығарады. «Екінші типтегі стирлингтер» деген атау осыдан шыққан.
Ыдырау EGF-ге тең
B ( з ) = эксп ( эксп з − 1 ) . { displaystyle B (z) = exp left ( exp z-1 right)} Алу үшін саралаңыз
г. г. з B ( з ) = эксп ( эксп з − 1 ) эксп з = B ( з ) эксп з , { displaystyle { frac {d} {dz}} B (z) = exp left ( exp z-1 right) exp z = B (z) exp z,} мұны білдіреді
B n + 1 = ∑ к = 0 n ( n к ) B к , { displaystyle B_ {n + 1} = sum _ {k = 0} ^ {n} {n k} B_ {k} таңдаңыз,} конволюциясы бойынша экспоненциалды генерациялау функциялары және EGF дифференциациясы бірінші коэффициенттің төмендеуіне және ығысуға байланысты B n +1з n /n !.
Екінші типтегі Стирлинг сандарының EGF бөлімі бөлімге кіретін әрбір ішкі жиынды терминмен белгілеу арқылы алынады U { displaystyle { mathcal {U}} ,}
B = ОРНАТУ ( U × ОРНАТУ ≥ 1 ( З ) ) . { displaystyle { mathcal {B}} = оператордың аты {SET} ({ mathcal {U}} times operatorname {SET} _ { geq 1} ({ mathcal {Z}})).} Функцияларды генерациялауға аударамыз
B ( з , сен ) = эксп ( сен ( эксп з − 1 ) ) . { displaystyle B (z, u) = exp left (u left ( exp z-1 right) right).} Бұл EGF екінші типтегі Стирлинг сандарының формуласын береді:
{ n к } = n ! [ сен к ] [ з n ] B ( з , сен ) = n ! [ з n ] ( эксп з − 1 ) к к ! { displaystyle left {{ begin {matrix} n k end {matrix}} right } = n! [u ^ {k}] [z ^ {n}] B (z, u) = n! [z ^ {n}] { frac {( exp z-1) ^ {k}} {k!}}} немесе
n ! [ з n ] 1 к ! ∑ j = 0 к ( к j ) эксп ( j з ) ( − 1 ) к − j { displaystyle n! [z ^ {n}] { frac {1} {k!}} sum _ {j = 0} ^ {k} {k select j} exp (jz) (- 1) ^ {кж}} жеңілдетеді
n ! к ! ∑ j = 0 к ( к j ) ( − 1 ) к − j j n n ! = 1 к ! ∑ j = 0 к ( к j ) ( − 1 ) к − j j n . { displaystyle { frac {n!} {k!}} sum _ {j = 0} ^ {k} {k select j} (- 1) ^ {kj} { frac {j ^ {n} } {n!}} = { frac {1} {k!}} sum _ {j = 0} ^ {k} {k таңдау j} (- 1) ^ {kj} j ^ {n}. } Әдебиеттер тізімі
Рональд Грэм , Дональд Кнут , Орен Паташник (1989): Бетонды математика , Аддисон – Уэсли, ISBN 0-201-14236-8Митринович Д. , Sur une classe de nombre Stirling aux nombres-ке сүйенеді , C. R. Acad. Ғылыми. Париж 252 (1961), 2354–2356.Белтон, Монотонды Пуассон процесі , ішінде: Кванттық ықтималдық (М. Бозейко, В. Млотковский және Дж. Висоцзанский, ред.), Банах орталығы басылымдары 73, Польша Ғылым Академиясы, Варшава, 2006 Милтон Абрамовиц және Айрин А. Стегун , Формулалары, графиктері және математикалық кестелері бар математикалық функциялар туралы анықтамалық , USGPO, 1964, Вашингтон, ISBN 0-486-61272-4
![[z ^ {n}]](https://wikimedia.org/api/rest_v1/media/math/render/svg/16378bf9f6c602c971e93212ae4fc4a18658fa9f)
![{ displaystyle G (z, u) = exp left (u log { frac {1} {1-z}} right) = left ({ frac {1} {1-z}} ) оң) ^ {u} = sum _ {n = 0} ^ { infty} sum _ {k = 0} ^ {n} left [{ begin {matrix} n k end {matrix} } right] u ^ {k} , { frac {z ^ {n}} {n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9b03c145e3a6dca53c5b8b983a0d099886606ed)
![{ displaystyle (-1) ^ {n-k} сол жақта [{ begin {matrix} n k end {matrix}} right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ee2adc72f418a3b3db07de990da9d16ef8f9317)
![{ displaystyle H (z, u) = G (-z, -u) = left ({ frac {1} {1 + z}} right) ^ {- u} = (1 + z) ^ { u} = sum _ {n = 0} ^ { infty} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k соңы {matrix}} right] u ^ {k} , { frac {z ^ {n}} {n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b593bd2afc37e0074a4e4f72d0883afa36c54504)
![{ displaystyle (1 + z) ^ {u} = sum _ {n = 0} ^ { infty} {u select n} z ^ {n} = sum _ {n = 0} ^ { infty } { frac {z ^ {n}} {n!}} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k соңы {matrix}} right] u ^ {k} = sum _ {k = 0} ^ { infty} u ^ {k} sum _ {n = k} ^ { infty} { frac {z ^ {n}} {n!}} (- 1) ^ {nk} left [{ begin {matrix} n k end {matrix}} right] = e ^ {u log (1+) z)}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a3a9c96d6694c2cb22364df476a972e8aa08d41)
![sum _ {{k = 0}} ^ {n} (- 1) ^ {k} left [{ begin {matrix} n k end {matrix}} right] = (- 1) ^ {n} n !.](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0fb7d6d9e8c79703544a251891d048c88d922f9)
![H (z, -1) = { frac {1} {1 + z}} quad { mbox {және бұдан}} quad n! [Z ^ {n}] H (z, -1) = ( -1) ^ {n} n !.](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b163f781f1c4e4fcb912cd5458123426b318c88)
![sum _ {{n = k}} ^ { infty} left [{ begin {matrix} n k end {matrix}} right] { frac {z ^ {n}} {n! }} = { frac { сол ( log (1 + z) оң) ^ {k}} {k!}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97f3bf2836729d248d4b9a372dddcdd648eeb4d8)
![[u ^ {k}] H (z, u) = [u ^ {k}] exp left (u log (1 + z) right) = { frac { left ( log (1+) z) right) ^ {k}} {k!}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6c88aea4798576902f921bb1268b67347580bbe)
![left {{ begin {matrix} n k end {matrix}} right } = n! [u ^ {k}] [z ^ {n}] B (z, u) = n! [z ^ {n}] { frac {( exp z-1) ^ {k}} {k!}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a67aa854ea914d34f8be2d5f6ea7f175ce9d75c)
![n! [z ^ {n}] { frac {1} {k!}} sum _ {{j = 0}} ^ {k} {k select j} exp (jz) (- 1) ^ {{kj}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e127b7f0efa5602037974f23a1a513f1e51fc65a)
