Stirling numbers and exponential generating functions in symbolic combinatorics
Использование экспоненциальные производящие функции (EGF)Числа Стирлинга комбинаторная математика и, возможно, канонический пример того, как символическая комбинаторика используется. Это также иллюстрирует параллели в построении этих двух типов чисел, обеспечивая поддержку биномиальной нотации, которая используется для них.
В этой статье используется оператор извлечения коэффициентов [ z п ] { Displaystyle [г ^ {п}]} формальный степенной ряд , а также (помеченные) операторы C { Displaystyle { mathfrak {C}}} п { displaystyle { mathfrak {P}}} символическая комбинаторика . Учитывая комбинаторный класс, оператор цикла создает класс, полученный путем размещения объектов из исходного класса вдоль цикла некоторой длины, где учитываются циклические симметрии, а оператор набора создает класс, полученный путем размещения объектов из исходного класса в набор (симметрии от симметрической группы, то есть «неструктурированный мешок»). Два комбинаторных класса (показаны без дополнительных маркеров):
перестановки (для беззнаковых чисел Стирлинга первого рода): п = НАБОР ( CYC ( Z ) ) , { displaystyle { mathcal {P}} = operatorname {SET} ( operatorname {CYC} ({ mathcal {Z}})),} и
B = НАБОР ( НАБОР ≥ 1 ( Z ) ) , { displaystyle { mathcal {B}} = operatorname {SET} ( operatorname {SET} _ { geq 1} ({ mathcal {Z}})),} куда Z { Displaystyle { mathcal {Z}}}
Предупреждение : Обозначение, используемое здесь для чисел Стирлинга, не такое, как в статьях Википедии о числах Стирлинга; квадратные скобки обозначают здесь числа Стирлинга со знаком.
Числа Стирлинга первого рода
Беззнаковые числа Стирлинга первого рода подсчитывают количество перестановок [п ] с k циклы. Подстановка - это набор циклов, и, следовательно, множество п { Displaystyle { mathcal {P}} ,}
п = НАБОР ( U × CYC ( Z ) ) , { displaystyle { mathcal {P}} = operatorname {SET} ({ mathcal {U}} times operatorname {CYC} ({ mathcal {Z}})), ,} где синглтон U { displaystyle { mathcal {U}}} статистика случайных перестановок .
Переходя к производящим функциям, мы получаем смешанную производящую функцию беззнаковых чисел Стирлинга первого рода:
грамм ( z , ты ) = exp ( ты бревно 1 1 − z ) = ( 1 1 − z ) ты = ∑ п = 0 ∞ ∑ k = 0 п [ п k ] ты k z п п ! . { Displaystyle G (z, и) = ехр влево (и журнал { гидроразрыва {1} {1-z}} справа) = влево ({ гидроразрыва {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 ) п − k [ п k ] . { displaystyle (-1) ^ {n-k} left [{ begin {matrix} n k end {matrix}} right].} Следовательно, производящая функция ЧАС ( z , ты ) { Displaystyle Н (г, и)}
ЧАС ( z , ты ) = грамм ( − z , − ты ) = ( 1 1 + z ) − ты = ( 1 + z ) ты = ∑ п = 0 ∞ ∑ k = 0 п ( − 1 ) п − k [ п k ] ты k z п п ! . { 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 end {matrix}} right] u ^ {k} , { frac {z ^ {n}} {n!}}.}.} Манипулируя этим, можно получить множество идентификационных данных. производящая функция :
( 1 + z ) ты = ∑ п = 0 ∞ ( ты п ) z п = ∑ п = 0 ∞ z п п ! ∑ k = 0 п ( − 1 ) п − k [ п k ] ты k = ∑ k = 0 ∞ ты k ∑ п = k ∞ z п п ! ( − 1 ) п − k [ п k ] = е ты бревно ( 1 + z ) . { displaystyle (1 + z) ^ {u} = sum _ {n = 0} ^ { infty} {u choose n} z ^ {n} = sum _ {n = 0} ^ { infty } { frac {z ^ {n}} {n!}} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k конец {матрица}} 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)}.} В частности, можно поменять порядок суммирования и взять производные, и тогда z или же ты может быть исправлено.
Конечные суммы Простая сумма
∑ k = 0 п ( − 1 ) k [ п k ] = ( − 1 ) п п ! . { displaystyle sum _ {k = 0} ^ {n} (- 1) ^ {k} left [{ begin {matrix} n k end {matrix}} right] = (- 1) ^ {п} п !.} Эта формула верна, потому что экспоненциальная производящая функция суммы равна
ЧАС ( z , − 1 ) = 1 1 + z и поэтому п ! [ z п ] ЧАС ( z , − 1 ) = ( − 1 ) п п ! . { Displaystyle H (z, -1) = { frac {1} {1 + z}} quad { mbox {и, следовательно,}} quad n! [z ^ {n}] H (z, -1 ) = (- 1) ^ {n} n !.} Бесконечные суммы Некоторые бесконечные суммы включают
∑ п = k ∞ [ п k ] z п п ! = ( бревно ( 1 + z ) ) k k ! { 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!}}} куда | z | < 1 { Displaystyle | г | <1} z = 0 { displaystyle z = 0} бревно ( 1 + z ) { Displaystyle журнал (1 + Z)} z = − 1. { displaystyle z = -1.}
Это соотношение выполняется, потому что
[ ты k ] ЧАС ( z , ты ) = [ ты k ] exp ( ты бревно ( 1 + z ) ) = ( бревно ( 1 + z ) ) k k ! . { Displaystyle [и ^ {к}] ЧАС (г, и) = [и ^ {к}] ехр влево (и журнал (1 + г) вправо) = { гидроразрыва { влево ( журнал (1 + z) right) ^ {k}} {k!}}.} Числа Стирлинга второго рода
Эти числа подсчитывают количество разделов [п ] в k непустые подмножества. Сначала рассмотрим общее количество разделов, т.е. B п
B п = ∑ k = 1 п { п k } и B 0 = 1 , { displaystyle B_ {n} = sum _ {k = 1} ^ {n} left {{ begin {matrix} n k end {matrix}} right } { mbox {and} } B_ {0} = 1,} то есть Номера звонков . В Основная теорема Флажоле – Седжвика. применяется (помеченный случай). B { Displaystyle { mathcal {B}} ,}
B = НАБОР ( НАБОР ≥ 1 ( Z ) ) . { displaystyle { mathcal {B}} = operatorname {SET} ( operatorname {SET} _ { geq 1} ({ mathcal {Z}})).} Это разложение полностью аналогично построению множества п { Displaystyle { mathcal {P}} ,}
п = НАБОР ( CYC ( Z ) ) . { displaystyle { mathcal {P}} = operatorname {SET} ( operatorname {CYC} ({ mathcal {Z}})).} и дает числа Стирлинга первого рода. Отсюда и название «числа Стирлинга второго рода».
Разложение эквивалентно EGF
B ( z ) = exp ( exp z − 1 ) . { Displaystyle В (z) = ехр влево ( ехр г-1 вправо).} Дифференцируйте, чтобы получить
d d z B ( z ) = exp ( exp z − 1 ) exp z = B ( z ) exp z , { Displaystyle { гидроразрыва {d} {dz}} В (z) = ехр влево ( ехр Z-1 справа) ехр Z = В (г) ехр г,} откуда следует, что
B п + 1 = ∑ k = 0 п ( п k ) B k , { displaystyle B_ {n + 1} = sum _ {k = 0} ^ {n} {n select k} B_ {k},} путем свертки экспоненциальные производящие функции и поскольку дифференцирование EGF снижает первый коэффициент и сдвигает B п +1z п /п !.
EGF чисел Стирлинга второго рода получается путем пометки каждого подмножества, входящего в раздел, термином U { Displaystyle { mathcal {U}} ,}
B = НАБОР ( U × НАБОР ≥ 1 ( Z ) ) . { displaystyle { mathcal {B}} = operatorname {SET} ({ mathcal {U}} times operatorname {SET} _ { geq 1} ({ mathcal {Z}})).} Переходя к производящим функциям, получаем
B ( z , ты ) = exp ( ты ( exp z − 1 ) ) . { Displaystyle В (г, и) = ехр влево (и влево ( ехр г-1 вправо) вправо).} Этот EGF дает формулу для чисел Стирлинга второго рода:
{ п k } = п ! [ ты k ] [ z п ] B ( z , ты ) = п ! [ z п ] ( exp z − 1 ) k k ! { displaystyle left {{ begin {matrix} n k end {matrix}} right } = n! [u ^ {k}] [z ^ {n}] B (z, u) = п! [z ^ {n}] { frac {( exp z-1) ^ {k}} {k!}}} или же
п ! [ z п ] 1 k ! ∑ j = 0 k ( k j ) exp ( j z ) ( − 1 ) k − j { displaystyle n! [z ^ {n}] { frac {1} {k!}} sum _ {j = 0} ^ {k} {k choose j} exp (jz) (- 1) ^ {кДж}} что упрощает
п ! k ! ∑ j = 0 k ( k j ) ( − 1 ) k − j j п п ! = 1 k ! ∑ j = 0 k ( k j ) ( − 1 ) k − j j п . { displaystyle { frac {n!} {k!}} sum _ {j = 0} ^ {k} {k choose j} (- 1) ^ {kj} { frac {j ^ {n} } {n!}} = { frac {1} {k!}} sum _ {j = 0} ^ {k} {k choose j} (- 1) ^ {kj} j ^ {n}. } Рекомендации
Рональд Грэм , Дональд Кнут , Орен Паташник (1989): Конкретная математика , Эддисон – Уэсли, ISBN 0-201-14236-8 Д. С. Митринович , Sur une classe de nombre полагается на aux nombres de Stirling , C.R. Acad. Sci. Париж 252 (1961), 2354–2356.А.С.Р. Белтон, Монотонный процесс Пуассона , в: Квантовая вероятность (М. Bozejko, W. Mlotkowski и J. Wysoczanski, ред.), Banach Center Publications 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, и) = ехр влево (и журнал { гидроразрыва {1} {1-z}} справа) = влево ({ гидроразрыва {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} left [{ 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 end {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 choose n} z ^ {n} = sum _ {n = 0} ^ { infty } { frac {z ^ {n}} {n!}} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k конец {матрица}} 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 { left ( log (1 + z) right) ^ {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 choose j} exp (jz) (- 1) ^ {{kj}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e127b7f0efa5602037974f23a1a513f1e51fc65a)
