Формула Стирленга

Оглавление
Введение
Глава 1. Формула Стирлинга
Общий вид формулы
Вывод формул Стирлинга
Числа Стирлинга
Число Стирлинга второго рода
Треугольник Стирлинга для числа подмножеств
Число Стирлинга первого рода
Применение формулы Стирлинга
Заключение
БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Формула Стирленга

5) превращается в приближенную формулу вычисления факториалов при больших значениях nприведем без вывода более точную формулу где в скобках стоит не сходящийся ряд.Числа СтирлингаЧисло Стирлинга второго рода Число Стирлинга второго рода S(n, k) равно количеству способов разбиения множества из n элементов на k непустых подмножеств и обозначается (читается “k подмножеств из n”). Например, существует 7 способов разбиения четырехэлементного множества на две части:{1, 2, 3} V {4}, {1, 2, 4} V {3}, {1, 3, 4} V {2}, {2, 3, 4} V {1},{1, 2} V {3, 4}, {1, 3} V {2, 4}, {1, 4} V {2, 3}Поэтому = 7.Рассмотрим значения чисел Стирлинга для малых значений k:1. k = 0. Существует только один способ разбиения пустого множества на нулевое число непустых частей, поэтому = 1. Для непустого множества нужна покрайней мере хотя бы одна часть, так что = 0 при n > 0.2. k = 1. Существует только один способ помещения n элементов в одно-единственное непустое множество, поэтому = 1 при n > 0. Однако = 0, так как 0-элементное множество пусто.3. k = 2. Очевидно, что = 0. Если множество из n > 0 объектов разделено на две непустые части, то одна из этих частей содержит последний объект и некоторое подмножество из n – 1 объектов. Имеется 2n-1 подмножеств из n – 1 объектов. Поскольку все объекты нельзя поместить в одну часть, то .n01101201130131401761501152510160131906515170163301350140211801127966170110502662819012553025777069512646462361Треугольник Стирлинга для числа подмножествВыведем рекуррентное соотношение, при помощи которого можно будет вычислить значения . Если задано множество из n > 0 объектов, которое должно быть разбито на k непустых частей, то мы либо помещаем последний объект в отдельный класс, а оставшиеся n – 1 объект разбиваем на k – 1 часть способами, либо помещаем его в любую из k частей, на которые разбиты n – 1 объект. В последнем случае имеется k * возможных вариантов, поскольку каждый из способов распределения первых n – 1 объектов по k непустым частям дает k подмножеств, с которыми можно объединить n -ый объект. Имеем рекуррентную формулу: = + k * , n > 0Число Стирлинга первого родаЧисло Стирлинга первого рода s(n, k) равно количеству способов представления n объектов в виде k циклов и обозначается (читается “k циклов из n”). Например, циклы из 4 элементов [a, b, c, d], [b, c, d, a], [c, d, a, b] и [d, a, b, c] являются одинаковыми. Цикл можно прокручивать, так как его конец соединен с началом.Например, существует 11 различных способов составить два цикла из четырех элементов:[1, 2, 3][4],[1, 2, 4][3],[1, 3, 4][2],[2, 3, 4][1],[1, 3, 2][4],[1, 4, 2][3],[1, 4, 3][2],[2, 4, 3][1],[1, 2][3, 4],[1, 3][2, 4],[1, 4][2, 3]Поэтому = 11.Единичный цикл (цикл, состоящий из одного элемента) – это то же самое, что и единичное множество. 2-цикл подобен 2-множеству, поскольку [A, B] = [B, A] как и {A, B} = {B, A}. Однако уже существует два различных 3-цикла: [A, B, C] и [A, C, B]. Из любого n-элементного множества могут быть составлены n! / n = (n – 1)! циклов, если n > 0 (всего имеется n! перестановок, а каждый цикл соответствует сразу n из них, так как отсчет цикла может быть начат с любого из его элементов). Поэтому = (n – 1)!.Если все циклы являются единичными или двойными, то = . Например, = = 1, = = Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление n объектов в виде k циклов либо помещает последний объект в отдельный цикл s(n – 1, k – 1) способами, либо вставляет этот объект в одно из s(n – 1, k) циклических представлений первых n – 1 объектов. В последнем случае существует n – 1 различных способов подобной вставки. Например, при вставке элемента d в цикл [a, b, c] можно получить только 3 разных цикла: [a, b, c, d], [a, b, d, c], [a, d, b, c]. Таким образом, рекуррентность имеет вид: = + (n – 1) * , n > 0N0110120113023140611615024503510160120274225851517072017641624735175211805040130681313267691960322281904032010958411812467284224494536546361Треугольник Стирлинга для числа цикловТеорема. Имеет место соотношение: Доказательство. обозначает число перестановок n объектов, которое содержит ровно k циклов. Если просуммировать по всем k, то должно получиться общее число перестановок, равное n!.