Числа Стирлинга

Числа Стирлинга, названные в честь Джеймса Стирлинга, имеют две разновидности и обычно называются числами Стирлинга первого и второго рода. Несмотря на долгую историю и многочисленные применения, для этих чисел до сих пор нет общепринятого обозначения. Воспользуемся обозначениями, введёнными Йованом Караматой, и будем записывать числа Стирлинга первого рода как $\stirlI{n}{k}$ , а числа Стирлинга второго рода — как $\stirlII{n}{k}$ . Числа Стирлинга второго рода встречаются чаще, поэтому они будут рассмотрены в первую очередь.

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

Число Стирлинга второго рода $\stirlII{n}{k}$ — число способов разбиения множества из $n$ элементов на $k$ непустых непересекающихся подмножеств.

Существует только один способ разделить пустое множество на $0$ непустых частей. А вот непустое множество невозможно разделить на $0$ непустых частей. Поэтому:

\stirlII{n}{0} = [n = 0]

Множество уже разделено на $1$ часть. Значит:

\stirlII{n}{1} = 1

Если множество разделено на $2$ непустые части, то в одной из частей должен содержаться первый элемент и ещё некоторое подмножество из $n-1$ оставшихся элементов. Всего подмножеств $2^{n-1}$ . Но подмножество не может содержать все оставшиеся элементы, потому что обе части должны быть непустыми. Значит:

\stirlII{n}{2} = 2^{n-1} - 1

Попробуем получить общую рекуррентную формулу. Первый элемент мы можем поместить в отдельный класс $\stirlII{n-1}{k-1}$ способами, либо мы можем поместить его в некоторое непустое множество из остальных $n-1$ элементов. В последнем случае имеется $k \cdot \stirlII{n-1}{k}$ возможных вариантов, потому что каждый из $\stirlII{n-1}{k}$ способов распределения первых $n-1$ объектов по $k$ непустым частям даёт $k$ подмножеств, с которыми можно объединить $n$ -ый объект. Следовательно:

\stirlII{n}{k} = k \cdot \stirlII{n-1}{k} + \stirlII{n-1}{k-1}

Как быть, если мы хотим приблизительно посчитать значение нужного нам числа Стирлинга второго рода? Пусть оно имеет вид $\stirlII{n+k}{n}$ . Если бы каждый элемент образовывал блок из одного элемента, число блоков было бы $n+k$ . Чтобы получить их ровно $n$ , нужно сократить количество блоков на $k$ , что возможно только за счёт объединения некоторых элементов. Тогда почему бы нам не создавать ровно $k$ блоков размера два и оставить остальные блоки одноэлементными. Выберем $2k$ элементов, которые войдут в пары.

\stirlII{n+k}{2k}

Теперь разобьем эти $2k$ выбранных элементов на $k$ неупорядоченных пар. Число таких разбиений известно:

(2k - 1)!! = \frac{(2k)!}{2^k \cdot k!}

Таким образом, число разбиений, в которых блоки имеют только размеры $1$ и $2$ , равно

\binom{n + k}{2k} \cdot \frac{(2k)!}{2^k k!} = \frac{(n + k)!}{(n - k)!} \cdot \frac{1}{2^k k!}

Разложим факториальную часть при больших $n$ :

\frac{(n + k)!}{(n - k)!} = (n - k + 1)(n - k + 2) \dots (n + k) = n^{2k} \left(1 + O\left(\frac{1}{n}\right)\right)

Отсюда получаем точную асимптотику:

\binom{n + k}{2k} \cdot (2k - 1)!! = \frac{n^{2k}}{2^k k!} + O\left(n^{2k - 1}\right)

Остаётся заметить, что любое разбиение, содержащее хотя бы один блок размера $\ge 3$ , включает в объединения меньше, чем $2k$ различных элементов. Значит, число таких разбиений есть многочлен по $n$ меньшей степени, чем $2k$ , и потому даёт вклад порядка $O(n^{2k - 1})$ . Следовательно, доминирующий член в асимптотике порождён разбиениями, содержащими ровно $k$ блоков размера два и остальные одноэлементные. Таким образом,

\stirlII{n + k}{n} = \frac{n^{2k}}{2^k k!} + O(n^{2k - 1}) \sim \frac{n^{2k}}{2^k \cdot k!}

Посмотрим на разбиение множества из $n+1$ элементов на $m+1$ непустых подмножеств. Рассмотрим один определённый элемент, пусть он входит в блок размера $k+1$ , тогда оставшиеся $k$ элементов этого блока можно выбрать $\binom{n}{k}$ способами, а остальные $n - k$ элементов разбиваются на $m$ блоков $\stirlII{n}{k}$ . Суммируем по всем $k$ и получаем:

\stirlII{n+1}{m+1} = \sum\limits_k \binom{n}{k} \stirlII{k}{m}

Посмотрим, что значит запись $m! \stirlII{n}{m}$ . Это количество способов разделить множество на m упорядоченных непустых подмножеств множества, состоящего из $n$ элементов. Теперь посчитаем, сколько существует распределений, где ровно $k$ подмножеств пусто.

\binom{m}{k} \cdot (m - k)^n

По формуле включений–исключений:

m! \cdot \stirlII{n}{m} = \sum\limits_{k=0}^{m} (-1)^k \cdot \binom{m}{k}(m - k)^n

Для красоты произведём замену $k = m - k$ :

m! \cdot \stirlII{n}{m} = \sum\limits_{k=0}^{m} \binom{m}{k} k^n \cdot (-1)^{m-k}

Продолжим делать необычные преобразования. Для этого запишем формулу в виде:

\stirlII{n}{m} = \frac{1}{m!} \sum\limits_{j=0}^{m} \binom{m}{j} \cdot j^n \cdot (-1)^{m-j}

Сначала произведём замену $m = m+1$ , $n = k+1$ , а потом просуммируем по $k$ обе части равенства и умножим на $\binom{n}{k} \, (-1)^{n-k}$ . Теперь равенство имеет следующий вид:

\sum\limits_{k \;\! = \;\! 0}^{n} \binom{n}{k} (-1)^{n-k} \stirlII{k+1}{m+1} = \sum\limits_{k \;\! = \;\! 0}^{n} \binom{n}{k} (-1)^{n-k} \frac{1}{(m + 1)!} \sum\limits_{j \;\! = \;\! 0}^{m+1} (-1)^{m+1-j} \binom{m+1}{j} \, j^{k+1}

В правой части поменяем порядок суммирования и заметим свёртку биномиальной суммы.

\align{ \sum\limits_{k \;\! = \;\! 0}^{n} \binom{n}{k} (-1)^{n-k} \stirlII{k+1}{m+1} &= \frac{1}{(m + 1)!} \sum\limits_{j \;\! = \;\! 0}^{m+1} (-1)^{m+1-j} \binom{m+1}{j} \, j \sum\limits_{k \;\! = \;\! 0}^{n} \binom{n}{k} (-1)^{n-k} \cdot j^k \\ &= \frac{1}{(m + 1)!} \sum\limits_{j \;\! = \;\! 0}^{m+1} (-1)^{m+1-j} \binom{m+1}{j} \, j \cdot (j-1)^n }

Так как в правой сумме есть множитель $j$ , то можно начинать сумму с $j = 1$ :

\align{ \sum\limits_{k \;\! = \;\! 0}^{n} \binom{n}{k} (-1)^{n-k} \stirlII{k+1}{m+1} &= \frac{1}{(m + 1)!} \sum\limits_{j \;\! = \;\! 1}^{m+1} (-1)^{m+1-j} \binom{m+1}{j} \, j \cdot (j-1)^n }

Сдвинем индексацию на один $j = j + 1$ и вынесем множитель из биномиального коэффициента.

\align{ \sum\limits_{k \;\! = \;\! 0}^{n} \binom{n}{k} (-1)^{n-k} \stirlII{k+1}{m+1} &= \frac{1}{(m + 1)!} \sum\limits_{j \;\! = \;\! 0}^{m+1} (-1)^{m-j} \binom{m+1}{j+1} \, (j+1) \cdot (j)^n = \\ &= \frac{1}{(m + 1)!} \sum\limits_{j \;\! = \;\! 0}^{m+1} (-1)^{m-j} \cdot \frac{m+1}{j+1} \cdot \binom{m}{j} \, (j+1) \cdot (j)^n = \\ &= \frac{1}{m!} \sum\limits_{j \;\! = \;\! 0}^{m+1} (-1)^{m-j} \cdot\binom{m}{j} \cdot (j)^n }

Можно сказать, что с этого мы и начинали. Теперь заменим правую часть равенства на $\stirlII{n}{m}$ и получим:

\stirlII{n}{m} = \sum\limits_{k \;\! = \;\! 0}^{n} \binom{n}{k} \stirlII{k+1}{m+1} (-1)^{n-k}

Одно из самых часто встречаемых свойств чисел Стирлинга это равенство, выражающее обычные степени $x^n$ через нисходящие $x^{\underline{n}}$ . Выглядит оно так:

x^n = \sum\limits_{k=0}^n \stirlII{n}{k} \, x^{\underline{k}} \quad{где}\ ~n \in \NN_0

Докажем по индукции $x \cdot x^{\underline{k}} = x^{\underline{k+1}} + k \cdot x^{\underline{k}}$ , потому что $x^{\underline{k+1}} = x^{\underline{k}} \cdot (x - k)$ , следовательно $x \cdot x^{\underline{n-1}}$ это:

\align{ x \cdot \sum\limits_{k} \stirlII{n-1}{k} \, x^{\underline{k}} &= \sum\limits_{k} \stirlII{n-1}{k} \, x^{\underline{k+1}} \, + \sum\limits_{k} \stirlII{n-1}{k} \, k x^{\underline{k}} \\ &= \sum\limits_{k} \stirlII{n-1}{k-1} \, x^{\underline{k}} \, + \sum\limits_{k} \stirlII{n-1}{k} \, k x^{\underline{k}} \\ &= \sum\limits_{k} \left( k \cdot \stirlII{n-1}{k} + \stirlII{n-1}{k-1} \right) x^{\underline{k}} = \sum\limits_{k} \stirlII{n}{k} x^{\underline{k}} }

Можно получить формулу, выражающую обычные степени $x^n$ через возрастающие $x^{\underline{n}}$ . Чтобы это сделать, начнём с производящей функции:

\sum\limits_{k=0}^{\oo} \frac{x^{\overline{k}}}{k!} p^k = (1 - p)^{-x}

Произведём замену $p = 1 - e^{-t}$ и получим:

\sum\limits_{k=0}^{\oo} \frac{x^{\overline{k}}}{k!} (1 - e^{-t})^k = (1 - (1 - e^{-t}))^{-x} =e^{xt}

Попробуем получить другую запись коэффициента $(1 - e^{-t})^k / k!$ . Для этого воспользуемся следующей производящей функцией:

\sum\limits_{n=k}^{\oo} \stirlII{n}{k} \, \frac{t^n}{n!} = \frac{(e^t - 1)^k}{k!}

Сделаем замену $t = -t$ и домножим на $(-1)^k$ :

\sum\limits_{n=k}^{\oo} \stirlII{n}{k} \, \frac{(-1)^{n-k} \, t^n}{n!} = \frac{(1 - e^{-t})^k}{k!}

Теперь можем подставить наше равенство как коэффициент $(1 - e^{-t})^k / k!$ :

e^{xt} = \sum\limits_{k=0}^{\oo} x^{\overline{k}} \Bigg( \sum\limits_{n=k}^{\oo} \stirlII{n}{k} \, \frac{(-1)^{n-k} \, t^n}{n!} \Bigg) = \sum\limits_{k=0}^{\oo} \sum\limits_{n=k}^{\oo} \stirlII{n}{k} \, \frac{(-1)^{n-k} \, t^n}{n!} x^{\overline{k}} = \sum\limits_{n=0}^{\oo} \frac{t^n}{n!} \sum\limits_{k \;\! = \;\! 0}^{n} \stirlII{n}{k} \, (-1)^{n-k} x^{\overline{k}}

Последним штрихом будет производящая функция для $e^{xt}$ :

\sum\limits_{n=0}^{\oo} \frac{t^n}{n!} x^n = e^{xt}

Коэффициенты при $t^n$ совпадают. Умножаем на $n!$ и получаем искомую формулу:

x^n = \sum\limits_{k \;\! = \;\! 0}^{n} \stirlII{n}{k} \, (-1)^{n-k} x^{\overline{k}}

Числа Стирлинга нашли свое применение и в теории вероятностей. Многие дискретные распределения — в частности, биномиальное — связаны со счётом числа успехов, выборов, перестановок или комбинаций. В итоге выражения для моментов таких распределений неизбежно содержат суммы, в которых встречаются степени целых чисел, а обычные степени несложно превратить в возрастающие или нисходящие. Давайте рассмотрим один из таких случаев. Пусть случайная величина $X$ имеет биномиальное распределение с параметрами $n$ и $p$ .

P(X = k) = \binom{n}{k} p^k (1-p)^{n-k} \quad{где} \ ~k = 0, 1, \dots, n

Наша цель — получить явное аналитическое выражение для произвольного момента $\EE[X^m]$ .

\EE[X^m] = \sum\limits_{k=0}^{n} k^m \binom{n}{k} p^k (1-p)^{n-k}

В таком виде выражение не позволяет проследить зависимость момента от параметров $n$ и $p$ . Чтобы преобразовать его, необходимо заменить обычную степень $k^m$ нисходящей степенью $k^{\underline{m}}$ , что приведёт к числам Стирлинга. Запишем нашу случайную величину с помощью чисел Стирлинга второго рода:

X^m = \sum\limits_{r=0}^{m} \stirlII{m}{r} \, X^{\underline{r}}

Так как математическое ожидание линейно, можем записать:

\EE[X^m] = \sum\limits_{r=0}^{m} \stirlII{m}{r} \, \EE[X^{\underline{r}}]

Таким образом, вычисление обычного момента сводится к нахождению моментов с ниcходящей степенью биномиального распределения.

Рассмотрим величину $X^{\underline{r}} = X(X-1) \dots (X-r+1)$ . По определению

\EE[X^{\underline{r}}] = \sum\limits_{k=0}^{n} k^{\underline{r}} \binom{n}{k} p^k (1-p)^{n-k}

Воспользуемся следующим комбинаторным тождеством:

k^{\underline{r}} \binom{n}{k} = n^{\underline{r}} \binom{n-r}{k-r}

Подставим это тождество.

\EE[X^{\underline{r}}] = \sum\limits_{k=r}^{n} n^{\underline{r}} \binom{n-r}{k-r} p^k (1-p)^{n-k}

Вынесем $n^{\underline{r}}$ и сгруппируем степени вероятности.

\EE[X^{\underline{r}}] = n^{\underline{r}} \cdot p^r \cdot \sum\limits_{k=r}^{n} \binom{n-r}{k-r} p^{k-r} (1-p)^{(n-r)-(k-r)}

Сделаем замену индекса $j = k - r$ .

\sum\limits_{j=0}^{n-r} \binom{n-r}{j} p^{j} (1-p)^{(n-r)-j} = (p + (1-p))^{n-r} = 1

Получаем компактную формулу факториального момента.

\EE[X^{\underline{r}}] = n^{\underline{r}} \cdot p^r

Подставляя найденное выражение факториальных моментов в нашу формулу, получаем итоговое выражение.

\EE[X^m] = \sum\limits_{r=0}^{m} \stirlII{m}{r} \, n^{\underline{r}} \cdot p^r

Это — общее замкнутое выражение для произвольного момента биномиальной случайной величины.

Теперь поговорим о распределении Пуасона. Оно занимает особое место в теории вероятностей. Это распределение описывает количество редких событий за фиксированное время или в фиксированной области: число аварий на перекрёстке за день, число звонков в колл-центр за минуту, количество радиоактивных распадов за интервал наблюдения и еще большой спектр случаев.

Главный параметр распределения Пуассона — число $\lambda > 0$ , которое одновременно является средним количеством событий и интенсивностью их появления. Случайная величина, имеющая распределение Пуассона с параметром $\lambda$ , обозначается как

X \sim \mathrm{Poisson}(\lambda)

и принимает значения $0,1,2,\dots$ с вероятностями:

P (X = m) = e^{-\lambda} \cdot \frac{\lambda^m}{m!} \quad{где} \ ~m = 0,1,2,\dots

Теперь вычислим математическое ожидание нисходящей степени случайной величины Пуассона, как делали это в биномиальном распределении. По определению

\EE[X^{\underline{k}}] = \sum\limits_{m=0}^{\oo} m^{\underline{k}} \, P(X = m)

Так как $m^{\underline{k}} = 0$ при $m < k$ , сумма начинается с $m = k$

\EE[X^{\underline{k}}] = \sum\limits_{m=k}^{\oo} m^{\underline{k}} \cdot e^{-\lambda} \cdot \frac{\lambda^m}{m!}

Поскольку $m^{\underline{k}} = m! / (m-k)!$ , имеем

\EE[X^{\underline{k}}] = e^{-\lambda} \sum\limits_{m=k}^{\oo} \frac{\lambda^m}{(m-k)!}

Сделаем замену индекса $j = m - k$ и получим

\EE[X^{\underline{k}}] = e^{-\lambda} \sum\limits_{j=0}^{\oo} \frac{\lambda^{j+k}}{j!} = e^{-\lambda} \cdot \lambda^k \sum\limits_{j=0}^{\oo} \frac{\lambda^j}{j!} = e^{-\lambda} \cdot \lambda^k \cdot e^{\lambda} = \lambda^k

Итак, моменты с нисходящей степенью распределения Пуассона имеют следующую форму:

\EE[X^{\underline{k}}] = \lambda^k

Теперь выразим обычные степени через нисходящие и воспользуемся линейностью математического ожидания:

\EE[X^n] = \sum\limits_{k=0}^{n} \stirlII{n}{k} \, \EE[X^{\underline{k}}]

Так как $\EE[X^{\underline{k}}] = \lambda^k$ , получаем итоговую формулу:

\EE[X^n] = \sum\limits_{k=0}^{n} \stirlII{n}{k} \, \lambda^k

Таким образом, каждый момент распределения Пуассона является полиномом от $\lambda$ , а коэффициенты перед степенями $\lambda^k$ — это числа Стирлинга второго рода.

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

Число Стирлинга первого рода $\stirlI{n}{k}$ — число перестановок $n$ объектов, содержащих ровно $k$ циклов.

Подробно о циклических перестановках можно почитать в соответствующей статье. Простым языком, циклическая перестановка $(1, 3, 2, 4)$ переводит элемент с позиции $1$ на позицию $3$ , $3$ — в $2$ , $2$ — в $4$ и, наконец, $4$ — в $1$ . Отмечу: единичный цикл — это, по сути, то же самое, что и множество, состоящее из одного элемента. Аналогично 2-цикл подобен 2-множеству, потому что $(1, 2) = (2, 1)$ — так же как и $\{1, 2 \} = \{2, 1 \}$ . Однако имеется два разных 3-цикла: $(1, 2, 3)$ и $(1, 3, 2)$ . В общем случае из любого $n$ -элементного множества можно составить $n!/n = (n - 1)!$ различных $n$ -циклов. Таким образом:

\stirlI{n}{1} = (n-1)! \quad{где} ~ \ ~n \in \NN

Это значительно больше величины $\stirlII{n}{1} = 1$ . Можно прийти к выводу, что каждое разбиение на непустые подмножества приводит как минимум к одному представлению в виде циклов. Значит:

\stirlI{n}{k} \ge \stirlII{n}{k} \quad{где} \ ~n,k \in \NN_0

Аналогично числам Стирлинга второго рода существует только один способ разделить множество на ноль циклов. Поэтому верно:

\stirlI{n}{0} = [n = 0]

Рекуррентное соотношение для чисел Стирлинга первого рода можно получить, изменив рассуждения, использовавшиеся при выводе чисел Стирлинга второго рода. Каждое представление $n$ объектов в виде $k$ циклов либо помещает последний объект в отдельный цикл $\stirlI{n-1}{k-1}$ способами, либо вставляет этот объект в одно $\stirlI{n-1}{k}$ из циклических представлений первых $n-1$ объектов. В последнем случае существует $n-1$ различных способов выполнения такой вставки. Это не очевидно, однако нетрудно убедиться, что имеется $j$ способов размещения нового элемента в $j$ -цикл для получения $j+1$ -цикла. Суммирование по всем $j$ даёт в итоге $n-1$ способов вставки $n$ -ого объекта в циклическое разбиение $n-1$ объектов. Таким образом, получаем рекуррентное соотношение:

\stirlI{n}{k} = (n-1) \cdot \stirlI{n-1}{k} + \stirlI{n-1}{k-1} \quad{где} \ ~n \in \NN

Посмотрим на связь циклов и некоторой перестановки $\alpha = (p_1, p_2, \dotsc , p_m)$ . Действительно, если начать с $m_0 = m$ и рассматривать $m_1 = p_{m_0}$ , $m_2 = p_{m_1}$ , и т.д., то в конце концов мы должны будем вернуться к $m_k = m_0$ . Числа раньше или позже должны будут повториться, и первым числом, которое появится вновь, будет именно $m_0$ , потому что мы знаем, что у других чисел $p_1, p_2, \dotsc , p_m$ имеются собственные уникальные предшественники. Каждая перестановка определяет некоторое циклическое представление. И обратно, каждое циклическое представление очевидным образом определяет перестановку. Следовательно, если просуммировать все $\stirlI{n}{k}$ по всем $k$ , то должно получиться общее количество перестановок:

\sum\limits_{k=0}^{n} \stirlI{n}{k} = n! \quad{где} \ ~n \in \NN

Рассуждения, используемые для чисел Стирлинга второго рода, применимы и для чисел Стирлинга первого рода. Возьмём перестановку из $n$ элементов и вставим в неё $n+1$ -й элемент: новый элемент может создать новый цикл или войти в уже существующий, не изменив их количества. Циклов, в которые мы можем добавить новый элемент, $\stirlI{n}{k}$ , а способов создать новые циклы на $m$ старых циклах существует $\binom{k}{m}$ . Снова суммируем по $k$ :

\stirlI{n+1}{m+1} = \sum\limits_k \binom{n}{k} \stirlI{k}{m}

Итак, доминирующее число перестановок с ровно $k$ двуциклами и остальными одноэлементными циклами равно

\binom{n + k}{2k} \cdot (2k - 1)!! = \binom{n + k}{2k} \cdot \frac{(2k)!}{2^k k!}

Разложим факториальную часть при больших $n$ :

\frac{(n + k)!}{(n - k)!} = (n - k + 1)(n - k + 2) \dots (n + k) = n^{2k}\Bigl(1 + O\!\bigl(\tfrac{1}{n}\bigr)\Bigr)

Отсюда получаем точную асимптотику:

\binom{n + k}{2k} \cdot (2k - 1)!! = \frac{n^{2k}}{2^k k!} + O(n^{2k - 1})

Если же перестановка содержит цикл длины $\ge 3$ , то в формировании непунктуальных циклов участвует меньше чем $2k$ элементов; следовательно, количество таких перестановок есть многочлен меньшей степени по $n$ . Поэтому вклад таких перестановок оказывается $O(n^{2k - 1})$ , и доминирует всё та же конфигурация из $k$ двуциклов. Отсюда следует асимптотика:

\stirlI{n+k}{n} = \frac{n^{2k}}{2^k k!} + O(n^{2k - 1}) \sim \frac{n^{2k}}{2^k k!}

Но узнать значение чисел Стирлинга первого рода мы можем и с помощью гармонических чисел. Для начала распишем рекурсивную формулу при $k = 2$ :

\stirlI{n+1}{2} = n \stirlI{n}{2} + (n-1)!

Разделим обе части на $n!$ :

\stirlI{n+1}{2} \cdot \frac{1}{n!} = \stirlI{n}{2} \cdot \frac{1}{(n-1)!} + \frac{1}{n}

Введем последовательность: $a_n = \stirlI{n+1}{2} / n!$ . Тогда наша рекурсивная формула приобретает следующий вид:

a_n = a_{n-1} + \frac{1}{n}

Начальное условие $a_1 = 1$ , тогда:

a_n = 1 + \sum\limits_{k=2}^{n} \frac{1}{k} = H_n

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

\stirlI{n+1}{2} = n! \cdot H_n

Давайте выведем общую формулу. Это будет немного сложнее, но старания окупятся. Приступим, посмотрим на произведение, которое по сути является восходящей степенью $(x+1)^{\overline{n+1}}$ . Это можно записать сразу двумя способами: через биномиальные коэффициенты и через числа Стирлинга первого рода.

Запишем производящую функцию для чисел Стирлинга первого рода по степени переменной $x$ . Эта формула показывает, что логарифмическая функция является их экспоненциальной производящей функцией.

\sum\limits_{n=k}^{\infty} \stirlI{n}{k} \frac{x^n}{n!} = \frac{1}{n!} \left( \ln(1 + x) \right)^k

Продифференцируем обе части.

\sum\limits_{n=k}^{\infty} \stirlI{n + 1}{k + 1} \frac{x^n}{n!} = \frac{1}{(k + 1)!} \left( \ln(1 + x) \right)^{k + 1}

Введём замену переменной $x = e^{-t} - 1$ , чтобы избавиться от логарифма в правой части и получить экспоненту.

\sum\limits_{n=k}^{\infty} \stirlI{n + 1}{k + 1} \frac{(e^{-t} - 1)^n}{n!} = \frac{(-t)^{k + 1}}{(k + 1)!}

Определим функцию $F(t)$ , которая естественным образом возникает после подстановки. Слева — аналитическая форма, справа — разложение через полиномиальные числа Бернулли.

F(t) = \left( \frac{t}{e^t - 1} \right)^{k+1} \cdot e^{-H_n t} = \sum\limits_{m=0}^{\infty} B_m^{(k+1)}(-H_n) \frac{t^m}{m!}

Теперь преобразуем знаменатель $(e^t - 1)^{k+1}$ , чтобы выразить его через числа Стирлинга первого рода.

\frac{1}{(e^t - 1)^{k+1}} = \frac{1}{t^{k+1}} \sum\limits_{m=0}^{\infty} \stirlI{m + k + 1}{k + 1} \frac{t^m}{(m + k + 1)!}

Подставим это разложение обратно в выражение для $F(t)$ и разложим экспоненту в степенной ряд — получим произведение двух рядов.

\align{ F(t) &= t^{k+1} e^{-H_n t} \cdot \frac{1}{t^{k+1}} \sum\limits_{m=0}^{\infty} \stirlI{m + k + 1}{k + 1} \frac{t^m}{(m + k + 1)!} = \\ &= \sum\limits_{i=0}^{\infty} (-1)^i (H_n)^i \frac{t^i}{i!} \sum\limits_{m=0}^{\infty} \stirlI{m + k + 1}{k + 1} \frac{t^m}{(m + k + 1)!} =\\ &= \sum\limits_{m=0}^{\infty} \sum\limits_{j=0}^{\infty} (-1)^j (H_n)^j \, \stirlI{m + k + 1}{k + 1} \frac{t^m}{(m + k + 1)! \, j!} }

Сделаем замену индексов $n = m + j$ и $m = n - j$ , чтобы собрать коэффициенты при одинаковых степенях $t^n$ .

F(t) = \sum\limits_{n=0}^{\infty} \sum\limits_{j=0}^{n} (-1)^j (H_n)^j \stirlI{\,n - j + k + 1\,}{k + 1} \frac{t}{j! \,(n - j + k + 1)!}

Теперь выражаем коэффициенты ряда — полиномиальные числа Бернулли — через числа Стирлинга первого рода и гармонические числа.

B_k^{(k+1)}(-H_n) = n! \sum\limits_{j=0}^{n} (-1)^j (H_n)^j \stirlI{\,n - j + k + 1\,}{k + 1} \frac{1}{j! \,(n - j + k + 1)!}

Получаем обратное тождество, выражающее числа Стирлинга первого рода через полиномиальные числа Бернулли.

\stirlI{n + 1}{k + 1} = \frac{n!}{k!} \sum\limits_{j=0}^{k} (-1)^j \binom{k}{j} B_{k - j}^{(k+1)} (-H_n) \cdot (H_n)^j

Уже было много неожиданных равенств, добавим еще. Мы захотим записать восходящую степень $x^{\underline{n}}$ через обычные степени $x^n$ , формула выглядит так:

x^{\overline{n}} = \sum\limits_{k=0}^n \stirlI{n}{k} x^k \quad{где} \ ~n \in \NN_0

Аналогично формуле для обычных степеней с числами Стирлинга второго рода, докажем по индукции $x^{\overline{k}} = x^{\overline{k-1}} \cdot (n + k)$ :

\align{ (x+n-1) \cdot \sum\limits_{k=0}^{n-1} \stirlI{n-1}{k} x^k &= \sum\limits_{k=1}^{n} \stirlI{n-1}{k-1} x^k + (n-1) \cdot \sum\limits_{k=0}^{n-1} \stirlI{n-1}{k} x^k = \\ &= \sum\limits_{k=1}^{n-1} \left( \stirlI{n-1}{k-1} + (n - 1) \cdot \stirlI{n-1}{k} \right) x^k + \stirlI{n-1}{n-1} x^{n} + (n-1) \cdot \stirlI{n-1}{0} x^0 = \\ &= \sum\limits_{k=1}^{n-1} \stirlI{n}{k} x^k + x^{n} + 0 = \sum\limits_{k=0}^n \stirlI{n}{k} x^k }

Чтобы вывести следующую формулу, сделаем замену $n = n + 1$ и $x = x - 1$ . Потом разделим на $(x - 1)$ :

x^{\overline{n}} = \sum\limits_{k=0}^{n} \stirlI{n+1}{k+1}(x-1)^k

Запишем $(x - 1)^k$ через биномиальные коэффициенты:

x^{\overline{n}} = \sum\limits_{k=0}^{n} \stirlI{n+1}{k+1} \sum\limits_{m=0}^{k} \binom{n}{m} x^m \cdot (-1)^{k-m}

Поменяем порядок суммирования и приравняем к изначальной формуле для $x^{\overline{n}}$ :

\sum\limits_{m=0}^n \stirlI{n}{m} x^m = \sum\limits_{m=0}^{n} \Bigg( \sum\limits_{k=m}^{k} \stirlI{n+1}{k+1} \binom{n}{m} \cdot (-1)^{k-m} \Bigg) x^m

Сравниваем коэффициенты при $x^m$ и получаем формулу:

\stirlI{n}{m} = \sum\limits_{k=m}^{k} \stirlI{n+1}{k+1} \binom{n}{m} \cdot (-1)^{k-m}

Выведем формулу для нисходящих степеней $x^{\underline{k}}$ через обычные $x^n$ , как и с числами Стирлинга второго рода, сделаем это с помощью производящих функций. Начнём с биномиальной формулы с обобщённым коэффициентом $\binom{x}{n} = x^{\underline{n}} / n!$ и производящей функции для $(1 + t)^x$ :

(1 + t)^x = \sum\limits_{n \;\! \ge \;\! 0} \binom{x}{n} t^n = \sum\limits_{n \;\! \ge \;\! 0} \frac{x^{\underline{n}}}{n!} t^n

С другой стороны:

(1 + t)^x = e^{x \ln{(1 + t)}} = \sum\limits_{n=0}^{\oo} \frac{x^n}{n!} (\ln{(1 + t)})^n

Попробуем найти, чему равен коэффициент $(\ln{(1 + t)})^n / n!$ . Посмотрим на другую экспоненциальную производящую функцию:

\sum\limits_{n=k}^{\oo} \stirlI{n}{k} \frac{t^n}{n!} = \frac{1}{k!} (-\ln{(1 - t)})^k

Как мы делали при выводе формулы с числами Стирлинга второго рода, заменим $t$ на $-t$ и умножим обе части на $(-1)^k$ :

\sum\limits_{n=k}^{\oo} \stirlI{n}{k} \frac{(-1)^{n-k} \cdot t^n}{n!} = \frac{1}{k!} (\ln{(1 + t)})^k

Отлично — теперь мы можем подставить значение $(\ln{(1 + t)})^n / n!$ в наше равенство:

(1 + t)^x = \sum\limits_{k=0}^{\oo} x^k \sum\limits_{n=k}^{\oo} \stirlI{n}{k} \frac{(-1)^{n-k} \cdot t^n}{n!} = \sum\limits_{n=0}^{\oo}\sum\limits_{k \;\! = \;\! 0}^{n} \stirlI{n}{k} \frac{(-1)^{n-k} \cdot t^n}{n!} x^k = \sum\limits_{n=0}^{\oo} \frac{t^n}{n!} \sum\limits_{k \;\! = \;\! 0}^{n} \stirlI{n}{k} (-1)^{n-k} \cdot x^k

Вернёмся к самому первому равенству, полученному для $(1 + t)^x$ . Так как серия по $t^n$ единственная, то коэффициенты при $t^n$ совпадают. Остаётся лишь умножить на $n!$ и получить желаемую формулу:

x^{\underline{n}} = \sum\limits_{k=0}^{n} \stirlI{n}{k} (-1)^{n-k} \cdot x^k

Связь между комбинаторикой и аналитической теорией чисел хорошо заметна тогда, когда в одном контексте появляются числа Стирлинга и дзета-функции Римана и Гурвица.

Отправной точкой служит тождество, которое связывает степени логарифма с числами Стирлинга первого рода.

\frac{\log^{m}(1+z)}{1+z} = m! \sum\limits_{k=0}^{\oo} \stirlI{k+1}{m+1} \cdot \frac{1}{k!} z^{k} \quad{где} \ ~|z| < 1

С этими же числами связано равенство для дзета-функции Римана:

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \cdot \frac{1}{n\,(n!)} = \zeta(i+1) \quad{где} \ ~i = 1, 2, 3, \dots

Если заменить факториал на восходящую степень, то можно получить выражение для дзета-функции Гурвица, обобщающей дзета-функцию Римана.

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \cdot \frac{1}{n \cdot v^{\overline{n}}} = \zeta(i+1, v) \quad{где} \ ~\Re(v) > 0

Их экспоненциальная производящая функция имеет вид:

\sum\limits_{n=k}^{\oo} \stirlI{n}{k} \frac{z^n}{n!} = \frac{(-1)^k}{k!} \ln^{k}(1 - z) \quad{где} \ ~|z| < 1

Рассматриваем интересующую нас величину

S_i = \sum\limits_{n=i}^{\oo} \stirlI{n}{i} \cdot \frac{1}{n \, n!}

Наличие множителя $1/n$ не дает воспользоваться производящей функцией напрямую, для этого сделаем замену:

\frac{1}{n} = \int\limits_{0}^{1} x^{n-1} dx

Подставляя это представление в сумму, получаем

\stirlI{n}{i} \cdot \frac{1}{n \cdot n!} = \stirlI{n}{i} \cdot \frac{1}{n!} \cdot \int\limits_{0}^{1} x^{n-1} dx

Суммируя по $n$ и меняя порядок суммирования и интегрирования, имеем

S_i = \int\limits_{0}^{1} \left( \sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{x^{n-1}}{n!} \right) dx

Преобразуем внутреннюю сумму. Из производящей функции следует

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{x^n}{n!} = \frac{(-1)^i}{i!} \ln^{i}(1 - x)

Домножим обе части на $x^{-1}$ , что допустимо при $x \in (0,1)$ :

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{x^{n-1}}{n!} = \frac{(-1)^i}{i!} \frac{\ln^{i}(1 - x)}{x}

Подставляя это выражение во внутреннюю сумму, получаем

S_i = \frac{(-1)^i}{i!} \int\limits_{0}^{1} \frac{\ln^{i}(1 - x)}{x} dx

Это выражение является ключевым переходом: в правой части появляется интеграл, в котором уже угадывается структура дзета-функции.

Сделаем замену переменной $t = 1 - x$ , тогда $dt = -dx$ . Получаем

\int\limits_{0}^{1} \frac{\ln^{i}(1 - x)}{x} dx = \int\limits_{1}^{0} \frac{\ln^{i}(t)}{1 - t} (-dt) = \int\limits_{0}^{1} \frac{\ln^{i}(t)}{1 - t} dt

Так как $\ln t < 0$ на интервале $(0,1)$ , верно равенство

(-1)^i \ln^{i}(t) = (-\ln t)^{i}

Подставляя это в выражение для $S_i$ , получаем

S_i = \frac{1}{i!} \int\limits_{0}^{1} \frac{(-\ln t)^{i}}{1 - t} dt

Теперь используем разложение в геометрический ряд

\frac{1}{1 - t} = \sum\limits_{m=0}^{\oo} t^{m} \quad{где} \ ~|t| < 1

и подставляем его в интеграл:

S_i = \frac{1}{i!} \sum\limits_{m=0}^{\oo} \int\limits_{0}^{1} t^{m} (-\ln t)^{i} dt

Интеграл в правой части вычисляется по известной формуле (её легко получить заменой $t = e^{-u}$ ):

\int\limits_{0}^{1} t^{m} (-\ln t)^{i} dt = \frac{i!}{(m+1)^{i+1}}

Подставляя это выражение, имеем

S_i = \sum\limits_{m=0}^{\oo} \frac{1}{(m+1)^{i+1}} = \sum\limits_{k=1}^{\oo} \frac{1}{k^{i+1}} = \zeta(i+1)

Тем самым получено окончательное тождество

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \cdot \frac{1}{n \cdot n!} = \zeta(i+1) \quad{где} \ ~i = 1, 2, 3, \dots

Это формула для дзета-функции Римона. Теперь наша цель — получить обобщение этой формулы для дзета-функции Гурвица. А именно, мы хотим доказать, что

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \cdot \frac{1}{n \cdot v^{\overline{n}}} = \zeta(i+1, v) \quad{где} \ ~i = 1, 2, 3, \dots, \, \Re(v) > 0

Восходящую степень также можно записать через гамма-функцию:

v^{\overline{n}} = v (v+1) \dots (v+n-1) = \frac{\Gamma(v+n)}{\Gamma(v)}

А дзета-функция Гурвица определяется рядом

\zeta(s, v) = \sum\limits_{m=0}^{\oo} \frac{1}{(m+v)^{s}} \quad{где} \ ~\Re(s) > 1 \ \Re(v) > 0

Из представления восходящей степени через гамма-функцию следует

\frac{1}{v^{\overline{n}}} = \frac{\Gamma(v)}{\Gamma(v+n)}

С другой стороны, бета-функция задаётся как

B(v, n) = \int\limits_{0}^{1} t^{v-1} (1 - t)^{n-1} dt = \frac{\Gamma(v) \cdot \Gamma(n)}{\Gamma(v+n)}

Отсюда получаем

\frac{\Gamma(v)}{\Gamma(v+n)} = \frac{1}{(n-1)!} \int\limits_{0}^{1} t^{v-1} (1 - t)^{n-1} dt

Таким образом,

\frac{1}{v^{\overline{n}}} = \frac{1}{(n-1)!} \int\limits_{0}^{1} t^{v-1} (1 - t)^{n-1} dt \quad{где} \ ~\Re(v) > 0 \ n \ge 1

Рассмотрим обобщённую сумму

S_i(v) = \sum\limits_{n=i}^{\oo} \stirlI{n}{i} \cdot \frac{1}{n \cdot v^{\overline{n}}}

Используя формулу выше, имеем

\frac{1}{n v^{\overline{n}}} = \frac{1}{n!} \int\limits_{0}^{1} t^{v-1} (1 - t)^{n-1} dt

Следовательно,

\stirlI{n}{i} \frac{1}{n v^{\overline{n}}} = \stirlI{n}{i} \frac{1}{n!} \int\limits_{0}^{1} t^{v-1} (1 - t)^{n-1} dt

Суммируя по $n \ge i$ и меняя порядок суммирования и интегрирования, получаем

S_i(v) = \int\limits_{0}^{1} t^{v-1} \left( \sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{(1 - t)^{n-1}}{n!} \right) dt

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

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{z^n}{n!} = \frac{(-1)^i}{i!} \ln^{i}(1 - z) \quad{где} \ ~|z| < 1

Подставляя $z = 1 - t$ получаем

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{(1 - t)^n}{n!} = \frac{(-1)^i}{i!} (\ln{t} )^{i}

Отделяя множитель $(1 - t)^{-1}$ приходим к

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{(1 - t)^{n-1}}{n!} = \frac{(-1)^i}{i!} \cdot \frac{(\ln{t} )^{i}}{1 - t}

Отсюда

S_i(v) = \frac{(-1)^i}{i!} \int\limits_{0}^{1} t^{v-1} \frac{\ln^{i}(t)}{1 - t} dt

Так как на интервале $(0,1)$ выполнено $(-1)^i \ln^{i}(t) = (-\ln t)^i$ , получаем

S_i(v) = \frac{1}{i!} \int\limits_{0}^{1} t^{v-1} \frac{(-\ln t)^i}{1 - t} dt

Разложим $1 / (1 - t)$ в геометрический ряд и подставим его под знак интеграла

S_i(v) = \frac{1}{i!} \sum\limits_{m=0}^{\oo} \int\limits_{0}^{1} t^{v-1+m} (-\ln t)^i dt

Интеграл в правой части вычисляется заменой $t = e^{-u}$ :

\int\limits_{0}^{1} t^{a-1} (-\ln t)^i dt = \frac{i!}{a^{i+1}}, \quad{где} \ ~\Re(a) > 0

В нашем случае $a = v + m$ , поэтому

S_i(v) = \sum\limits_{m=0}^{\oo} \frac{1}{(v + m)^{i+1}}

По определению это и есть дзета-функция Гурвица:

\sum\limits_{m=0}^{\oo} \frac{1}{(v + m)^{i+1}} = \zeta(i+1, v)

Объединяя результаты, получаем окончательное тождество

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{1}{n \cdot v^{\overline{n}}} = \zeta(i+1, v) \quad{где} \ ~i = 1, 2, 3, \dots, \ \Re(v) > 0

При $v = 1$ имеем $1^{\overline{n}}= n!$ , и формула вырождается в то, что мы уже выводили:

\sum\limits_{n=i}^{\oo} \stirlI{n}{i} \frac{1}{n \cdot n!} = \zeta(i+1)

Дополнительные тождества

Используя две формулы: для обычных степеней $x^n$ через восходящие степени $x^{\overline{n}}$ и для нисходящих степеней $x^{\underline{n}}$ через обычные степени $x^n$ , можно получить следующее равенство:

x^n = \sum\limits_k \stirlII{n}{k}(-1)^{n-k} \, x^{\overline{k}} = \sum\limits_{k, m} \stirlII{n}{k}\stirlI{n}{m}(-1)^{n-k} \, x^{m}

Это справедливо при всех $x$ , так что коэффициенты при $x^0, x^1, x^2, \dotsc , x^{n-1}, x^{n+1}, x^{n+2}$ должны быть равны нулю, и мы получаем тождество:

\sum\limits_{k} \stirlII{n}{k}\stirlI{k}{m}(-1)^{n-k} = [m=n] \quad{где} \ ~n, m \in \NN_0

Можно и наоборот. Для этого понадобятся формула для восходящих степеней $x^{\overline{n}}$ через обычные степени $x^{\overline{n}}$ и для обычных степеней $x^n$ через восходящие $x^{\overline{n}}$ :

x^{\overline{n}} = \sum\limits_{k \;\! = \;\! 0}^{n} \stirlI{n}{k} x^k = \sum\limits_{k, m} \stirlI{n}{k}\stirlII{n}{m}(-1)^{n-k} \, x^{\overline{m}}

Еще можно определить числа Стирлинга $\stirlI{n}{k}$ , $\stirlII{n}{k}$ для отрицательных $n$ . Сделать это не сложно, так как у нас уже есть базовые рекуррентные соотношения. Нам нужно ввести дополнительные соглашения:

\align{ \stirlI{0}{k} &= \stirlII{0}{k} = [k = 0]\\[0.8em]\stirlI{n}{0} &= \stirlII{n}{0} = [n = 0] }

Теперь числа Стирлинга первого и второго рода связывает простой закон:

\stirlI{n}{k} = \stirlII{-n}{-k} \quad{где} \ ~n, m \in \NN

Числа Стирлинга

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