2.3. Рекурсивное соотношение между числами Стирлинга второго рода
Для нахождения чисел Стирлинга второго рода может быть применено уравнение (2.1). Однако если требуется найти последовательность значений этих чисел, то удобнее воспользоваться рекуррентным соотношением, связывающим эти величины
Эта формула следует прежде всего из того, что
Откуда
Пользуясь определением
найдем:
и
Воспользовавшись равенством (2.13), из (2.15) получим:
Но поскольку
,
Сравнивая этот результат с (2.4), мы имеем:
Эквивалентной формулой для
является
откуда получаем:
При
каждый член суммы за исключением последнего стремится к нулю, поэтому
Таким образом, при больших
В табл. 2.1 приводятся значения
для
, не превышающих 8.
Таблица 2.1. Число разбиений на кластеры для различных значений