Главная > Математика > Введение в прикладную комбинаторику
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 10. Основные последовательности и формулы для пересчета

Числа Стирлинга. Рассмотрим производящую функцию

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

Обозначим через коэффициент при в разложении (10.1) и тогда запишем

Целые числа называются числами Стирлинга первого рода. Рассмотрим следующие тождества:

Обозначим через коэффициент при в разложении такого вида и запишем

Целые числа называются числами Стирлинга второго рода. В таблицах 10.1 и 10.2 приведены числа до

Для простоты полагают также

Таблица 10.1 (см. скан) Таблица чисел Стирлинга первого рода до

Таблица 10.2 (см. скан) Таблица чисел Стирлинга второго рода

Рекуррентные формулы для чисел Стирлинга. Имеем

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

Приравнивая коэффициенты при одинаковых степенях в правой и левой частях (10.8), получаем рекуррентную формулу:

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

Чтобы получить рекуррентную формулу для чисел Стирлинга второго рода, воспользуемся (10.5):

Представляя можно записать

В силу (10.7)

Подставляем (10.13) в (10.12):

Сравнивая (10.11) и (10.14), имеем

Приравниваем коэффициенты при в правой и левой частях (10.15):

Например,

Между числами и существует важное соотношение. Подставим (10.5) в (10.3):

Сравнивая выражения при в правой и левой частях (10.18), получаем

Пользуясь символом Кронекера

записываем

Если подставим, наоборот, (10.3) в (10.5), то получим симметричное соотношение:

Рассмотрим две бесконечные матрицы:

и

С их помощью (10.20) и (10.21) можно записать так:

где — единичная матрица бесконечного порядка.

Итак,

т. е. взаимно обратные матрицы.

Числа Белла. Полагаем

Элементы матриц назовем соответственно числами Белла первого и второго рода порядка

Числа Белла порядка - это числа Стирлинга.

Из (10.25), (10.26), (10.27) видно, что

Если обозначить элементы соответственно через то

Полиномы Белла и формула Бруно. Рассмотрим сложную функцию

Последовательные производные запишутся так:

Можно ли дать общий вид этих формул? Ответ утвердительный. Мы докажем следующую формулу, называемую формулой Бруно, правая часть которой называется голиномоч Белла. Оба эти понятия часто используются в комбинаторике

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

где такие целые неотрицательные числа, что а суммирование производится по всем решениям уравнения

Правые части для называются полиномами Белла.

Докажем (10 36), следуя Риордану [36]. Любая производная - линейная функция производных коэффициенты которой являются функциями производных

где

Так как не зависят от то для определения функцию можно выбрать произвольно. Возьмем

где а — действительное число, отличное от нуля.

Тогда

Подставим (10.40) в (10.37):

или

Полагаем

Перепишем (10.42), учитывая (10.43):

Согласно (10.44)

Таким образом, символически можно записать

При из этой формулы вытекает

К обеим частям (10.46) применим экспоненциальное -преобразование. По формулам (7.74) — (7.77) получаем

или

Интегрируем (10.49) от 0 до

Потенцируем (10.50):

Переходя к несимволическим обозначениям, получаем

Приравнивая коэффициенты при одинаковых степенях в (10.52), приходим к (10.47). Бруно дал следующую общую формулу, получаемую этим способом:

где целые неотрицательные числа и суммирование производится по всем решениям уравнения

Переходя от коэффициентов к производным имеем окончательно

В заключение приведем полиномы Белла для :

Числа Стирлинга и числа Покажем, что числа Стирлинга второго рода и числа связаны простым и интересным соотношением, которое будет использоваться в дальнейшем. Напомним рекуррентное соотношение (10.16), определяющее числа Стирлинга второго рода:

и рекуррентное соотношение (6.40) для

Обозначим

Умножаем обе части (10.56) на

Отсюда

Так как начальные значения совпадают для всех и рекуррентные соотношения, порождающие также совпадают, то

Таким образом, таблицы 6.1 и 10.2 могут быть получены одна из другой.

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

В самом деле, пусть - распределение вероятностей случайной величины

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

Рассмотрим производящую функцию для

Беря последовательные производные по 2 и полагая затем легко получаем

Числа дают возможность последовательно вычислить

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

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

Можно определить также моменты третьего типа, биномиальные моменты)

Между имеет место символическое соотношение

Таким образом, опять приходим к числам Стирлинга первого рода

и второго рода

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

Предварительно обозначим

Осуществим разложения

(см. скан)

Итак,

Рассмотрим разложение

(см. скан)

Обозначим

Сравнивая (10.74) и (10.75), получаем

Выпишем символическое представление

Итак,

где в некоторых из этих формул предполагается, что

Из (10.80) вытекает

Напомним, что

Представим правую часть (10.82) в следующем виде:

Сравниваем (10.83) и (10.84) относительно

Разлагаем

Подставляя (10.86) в (10.85), получаем из этого символического разложения

Наконец, ввиду (10.67) имеем 00

Это — соотношение, обратное к (10.67).

УПРАЖНЕНИЯ

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление