Рекуррентные соотношения для чисел Стирлинга второго рода

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

Правила решений рекурсивных соотношений вида (2)

Доказательство

Пусть

то есть получили аналог

Для соотношения (2) составленное квадратное уравнение вида (3) называется характеристическим, если это уравнение будет иметь 2 различных корня и то общее решение (2) будет иметь вид

(4)

Любое решение рекурсивного соотношения однозначно определено двумя значениями, подставим их в уравнение (4) получим:

(5)

Получили линейное уравнение

Общее решение этой системы будет:

Решение имеет место для любых a и b и можно всегда найти значение и то есть решение всегда есть и имеет единственное значение, в результате его можно представить в виде уравнения (4).

Пример: Пусть дано уравнение – Рекурсивное соотношение 2-го порядка. Если положив в это уравнение и, то в результате получим рекурсивное соотношение, которое определяет последовательность чисел полученных Фибоначчи.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 59, 114, 173.

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

Характеристическое уравнение для этой последовательности чисел будет:

, где, а.

Общее решение:

Требуется найти значения и соответственно заданным начальным требованиям:.

Берем n = 1,

Итак, общее решение будет иметь вид (числа Фибоначчи):

Пусть корни уравнения будут равные, то есть (корень кратный).

(7) и далее по аналогии.

Если имеется рекурсивное соотношение k-го порядка вида (1)

Если корни этого характеристического уравнения будут различны, то общее решение его будет:

Пример: Пусть этому корню кратности s в выражении (9) будет соответствовать своя сумма в выражении для общего решения уравнения

, n=1,2,3… - производящая функция.

Полагают, что

Эту производящую функцию назвали производящей многочлен степени n,.

Раскроем скобки в правой части через

Чтобы формула была справедлива, полагают, что: (); (); ().

Коэффициент при, то есть числа и назвали числами Стирлинга первого рода.

Выразим различные степени переменной t через факториальные многочлены.

Любую степень числа t можно записать

(); (); () Полагают для удобства, симметрия чисел Стирлинга.

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

Рассмотрим рекурсивное соотношение для чисел Стирлинга из (1) следует, что (4)

Воспользуемся формулой (2) и получим:

Коэффициент приравняем при степени k, получим:

то есть получим рекуррентное соотношение для чисел Стирлинга первого рода.

Коэффициенты в правой части в выражении 6 получены из (5a)

(7)

(8)

Нам известно, что
подставим в (8) выражение, получим:

и

(9)

Для равенства необходимо, чтобы коэффициенты при факториальных многочленах совпадали по степени k, тогда:

(10)

или + (10’)

-1

Дата добавления: 2014-01-05