Числа Стирлинга и экспоненциальные производящие функции в символьной комбинаторике

Использование экспоненциальных производящих функций (ЭФФ) для изучения свойств чисел Стирлинга является классическим упражнением в комбинаторной математике и, возможно, каноническим примером символической комбинаторики использования . Он также иллюстрирует параллели в построении этих двух типов чисел, поддерживая используемую для них биномиальную систему обозначений.

В этой статье используется оператор извлечения коэффициентов $[z^{n}]$ для формальных степенных рядов , а также (помеченных) операторов ${\mathfrak {C}}$ (для циклов) и ${\mathfrak {P}}$ (для множеств) по комбинаторным классам, которые описаны на странице символической комбинаторики . Учитывая комбинаторный класс, оператор цикла создает класс, полученный размещением объектов исходного класса по циклу некоторой длины, где учитываются циклические симметрии, а оператор множества создает класс, полученный размещением объектов исходного класса в набор (симметрии из симметричной группы, т.е. «неструктурированный мешок».) Два комбинаторных класса (показаны без дополнительных маркеров)

• перестановки (для беззнаковых чисел Стирлинга первого рода):

${\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})),$

и

• задать разбиения на непустые подмножества (для чисел Стирлинга второго рода):

${\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})),$

где ${\mathcal {Z}}$ это одноэлементный класс.

Предупреждение : обозначения, используемые здесь для чисел Стирлинга, не совпадают с обозначениями в статьях Википедии о числах Стирлинга; квадратные скобки здесь обозначают числа Стирлинга со знаком.

Числа Стирлинга первого рода

Беззнаковые числа Стирлинга первого рода подсчитывают количество перестановок [ n ] с k циклами. Перестановка — это набор циклов, а значит, и множество ${\mathcal {P}}\,$ перестановок определяется выражением

${\mathcal {P}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {CYC} ({\mathcal {Z}})),\,$

где синглтон ${\mathcal {U}}$ отмечает циклы. Более подробно это разложение рассматривается на странице статистики случайных перестановок .

Переводя к производящим функциям, получаем смешанную производящую функцию беззнаковых чисел Стирлинга первого рода:

$G(z,u)=\exp \left(u\log {\frac {1}{1-z}}\right)=\left({\frac {1}{1-z}}\right)^{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-k}\left[{\begin{matrix}n\\k\end{matrix}}\right].$

Следовательно, производящая функция $H(z,u)$ из этих чисел

$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)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.$

можно получить множество тождеств Манипулируя этой производящей функцией, :

$(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)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=e^{u\log(1+z)}.$

В частности, можно поменять порядок суммирования и взять производные, а затем z или u зафиксировать .

Конечные суммы

Простая сумма – это

$\sum _{k=0}^{n}(-1)^{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=(-1)^{n}n!.$

Эта формула справедлива, поскольку экспоненциальная производящая функция суммы равна

$H(z,-1)={\frac {1}{1+z}}\quad {\mbox{and hence}}\quad n![z^{n}]H(z,-1)=(-1)^{n}n!.$

Бесконечные суммы

Некоторые бесконечные суммы включают в себя

$\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$ (ближайшая к $z=0$из $\log(1+z)$ находится в $z=-1.$)

Это соотношение имеет место, поскольку

$[u^{k}]H(z,u)=[u^{k}]\exp \left(u\log(1+z)\right)={\frac {\left(\log(1+z)\right)^{k}}{k!}}.$

Числа Стирлинга второго рода

Эти числа подсчитывают количество разбиений [ n ] на k непустые подмножества. Сначала рассмотрим общее количество разделов, т. е. B _n , где

$B_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}{\mbox{ and }}B_{0}=1,$

т.е. числа Белла . Применяется фундаментальная теорема Флажоле – Седжвика (обозначенный случай).Набор ${\mathcal {B}}\,$ разбиений на непустые подмножества задается формулой («набор непустых наборов одиночных элементов»)

${\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).$

Это разложение полностью аналогично построению множества ${\mathcal {P}}\,$ перестановок из циклов, который определяется выражением

${\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})).$

и дает числа Стирлинга первого рода. Отсюда и название «числа Стирлинга второго рода».

Разложение эквивалентно EGF

$B(z)=\exp \left(\exp z-1\right).$

Дифференцируем, чтобы получить

${\frac {d}{dz}}B(z)=\exp \left(\exp z-1\right)\exp z=B(z)\exp z,$

что подразумевает, что

$B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k},$

путем свертки экспоненциальных производящих функций и потому, что при дифференцировании EGF отбрасывается первый коэффициент и сдвигается B _{n +1} на z  ^н / н !.

ЭФР чисел Стирлинга второго рода получается путем маркировки каждого подмножества, входящего в разбиение, термином ${\mathcal {U}}\,$, давая

${\mathcal {B}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {SET} _{\geq 1}({\mathcal {Z}})).$

Переводя к производящим функциям, получаем

$B(z,u)=\exp \left(u\left(\exp z-1\right)\right).$

Этот ЭФР дает формулу для чисел Стирлинга второго рода:

$\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![z^{n}]{\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}\exp(jz)(-1)^{k-j}$

что упрощается до

${\frac {n!}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}{\frac {j^{n}}{n!}}={\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}j^{n}.$

Ссылки

• Рональд Грэм , Дональд Кнут , Орен Паташник (1989): Конкретная математика , Аддисон-Уэсли, ISBN   0-201-14236-8
• Д. С. Митринович , Об одном классе чисел, связанных с числами Стирлинга , CR Acad. наук. Париж 252 (1961), 2354–2356.
• АКР Белтон, Монотонный процесс Пуассона , в: Квантовая вероятность (М. Божейко, В. Млотковский и Ю. Высочанский, ред.), Публикации Банахового центра 73, Польская академия наук, Варшава, 2006 г.
• Милтон Абрамовиц и Ирен А. Стеган , Справочник по математическим функциям с формулами, графиками и математическими таблицами , USGPO, 1964, Вашингтон, округ Колумбия, ISBN   0-486-61272-4