В математике , особенно в комбинаторике , число Стирлинга второго рода (или число разбиения Стирлинга ) — это количество способов разделить набор из n объектов на k непустые подмножества и обозначается или . [1] Числа Стирлинга второго рода встречаются в области математики , называемой комбинаторикой , и изучении разделов . Они названы в честь Джеймса Стирлинга .
Числа Стирлинга первого и второго рода можно понимать как обратные друг другу, если рассматривать их как треугольные матрицы . Данная статья посвящена особенностям чисел Стирлинга второго рода. Тождества, связывающие эти два вида, появляются в статье о числах Стирлинга .
Определение
Числа Стирлинга второго рода, записанные или с другими обозначениями, подсчитывают количество способов разбить набор помеченных объектов на непустые немаркированные подмножества. Эквивалентно, они подсчитывают количество различных отношений эквивалентности с точными классами эквивалентности, которые могут быть определены в наборе элементов. Фактически, существует биекция между множеством разбиений и множеством отношений эквивалентности на данном множестве. Очевидно,
для n ≥ 0 и для n ≥ 1
поскольку единственный способ разбить набор из n -элементов на n частей — это поместить каждый элемент набора в отдельную часть, а единственный способ разбить непустое множество на одну часть — это поместить все элементы в одну и ту же часть. . В отличие от чисел Стирлинга первого рода , их можно вычислить по формуле одной суммы: [2]
Числа Стирлинга второго рода можно также охарактеризовать как числа, возникающие при выражении степеней неопределенного x через падающие факториалы [3]
(В частности, ( x ) 0 = 1, поскольку это пустой продукт .)
Другими словами
Обозначения
Для чисел Стирлинга второго рода использовались различные обозначения. Фигурные скобки использовались Имануэлем Марксом и Антонио Салмери в 1962 году для вариантов этих чисел. [4] [5] Это побудило Кнута использовать его, как показано здесь, в первом томе « Искусства компьютерного программирования» (1968). [6] [7] Согласно третьему изданию «Искусства компьютерного программирования» , это обозначение также использовалось ранее Йованом Караматой в 1935 году. [8] [9] Обозначение S ( n , k ) использовалось Ричардом Стэнли в его книга «Перечислительная комбинаторика» , а также, гораздо раньше, многие другие авторы. [6]
Используемые на этой странице обозначения чисел Стирлинга не являются универсальными и могут противоречить обозначениям в других источниках.
Связь с числами Белла
Поскольку число Стирлинга учитывает разбиение набора из n -элементов на k частей, сумма
по всем значениям k — общее количество разделов набора из n членов. Это число известно как n -е число Белла .
Ниже представлен треугольный массив значений чисел Стирлинга второго рода (последовательность A008277 в OEIS ):
Как и в случае с биномиальными коэффициентами , эту таблицу можно расширить до k > n , но все записи будут равны 0.
Характеристики
Рекуррентное отношение
Числа Стирлинга второго рода подчиняются рекуррентному соотношению
с начальными условиями
Например, число 25 в столбце k = 3 и строке n = 5 определяется как 25 = 7 + (3×6), где 7 — это число выше и слева от 25, 6 — это число выше 25 и 3. это столбец, содержащий 6.
Чтобы доказать эту повторяемость, заметим, что разбиение объектов на k непустые подмножества либо содержит -й объект как одиночный, либо нет. Количество способов, которыми синглтон является одним из подмножеств, определяется выражением
поскольку мы должны разделить оставшиеся n объектов на доступные подмножества. В другом случае -ый объект принадлежит подмножеству, содержащему другие объекты. Количество способов определяется выражением
поскольку мы разделяем все объекты, кроме -го, на k подмножеств, и тогда у нас остается k вариантов вставки объекта . Суммирование этих двух значений дает желаемый результат.
Это связано с тем, что разделение n элементов на n - 1 наборов обязательно означает разделение его на один набор размера 2 и n - 2 набора размера 1. Поэтому нам нужно выбрать только эти два элемента;
и
Чтобы убедиться в этом, сначала заметим , что существует 2 n упорядоченных пар дополнительных подмножеств A и B. В одном случае A пусто, а в другом B пусто, поэтому остается 2 n − 2 упорядоченных пары подмножеств. Наконец, поскольку нам нужны неупорядоченные пары, а не упорядоченные , мы делим последнее число на 2, получая результат, указанный выше.
Другое явное расширение рекуррентного отношения дает тождества в духе приведенного выше примера.
Личности
Таблица в разделе 6.1 « Конкретной математики» содержит множество обобщенных форм конечных сумм, включающих числа Стирлинга. В число конкретных конечных сумм, имеющих отношение к этой статье, входят:
Явная формула
Числа Стирлинга второго рода задаются явной формулой:
Это можно получить, используя метод включения-исключения для подсчета сюръекций от n до k и используя тот факт, что количество таких сюръекций равно .
Четность центрального числа Стирлинга второго рода нечетна тогда и только тогда, когда является фиббинарным числом , числом, двоичное представление которого не имеет двух последовательных единиц. [11]
Генерирующие функции
Для фиксированного целого числа n обычная производящая функция для чисел Стирлинга второго рода имеет вид
где – полиномы Тушара . Если вместо этого суммировать числа Стирлинга с падающим факториалом, можно, среди прочего, показать следующие тождества:
и
Что имеет особый случай
.
Для фиксированного целого числа k числа Стирлинга второго рода имеют рациональную обычную производящую функцию
Также существует равномерно допустимое приближение: для всех k таких, что 1 < k < n , имеет место
где , и является единственным решением . [14] Относительная ошибка ограничена примерно .
Максимум для фиксированного n
При фиксированном имеет единственный максимум, который достигается не более чем для двух последовательных значений k . То есть существует целое число такое, что
Глядя на таблицу значений выше, первые несколько значений :
Когда большой
а максимальное значение числа Стирлинга можно аппроксимировать формулой
В частности, n- й момент распределения Пуассона с ожидаемым значением 1 — это в точности количество разбиений множества размера n , т. е. это n -е число Белла (этот факт и есть формула Добиньского ).
Числа Стирлинга второго рода могут представлять общее количество схем рифм для стихотворения из n строк. дает количество возможных схем рифмования для n строк с использованием k уникальных рифмующихся слогов. Например, для стихотворения из 3 строк предусмотрена 1 схема рифмы с использованием всего одной рифмы (ааа), 3 схемы рифмы с использованием двух рифм (ааб, аба, абб) и 1 схема рифмы с использованием трех рифм (abc).
Варианты
r -числа Стирлинга второго рода
r - число Стирлинга второго рода подсчитывает количество разбиений набора из n объектов на k непустые непересекающиеся подмножества, так что первые r элементов находятся в разных подмножествах. [15] Эти числа удовлетворяют рекуррентному соотношению
Некоторые комбинаторные тождества и связь между этими числами и контекстно-свободными грамматиками можно найти в [16].
Ассоциированные числа Стирлинга второго рода
Число Стирлинга второго рода, связанное с r, — это количество способов разбить набор из n объектов на k подмножеств, каждое из которых содержит не менее r элементов. [17] Оно обозначается и подчиняется рекуррентному соотношению
2-ассоциированные числа (последовательность A008299 в OEIS ) появляются в других местах как «числа Уорда» и как величины коэффициентов полиномов Малера .
Приведенные числа Стирлинга второго рода
Обозначим n объектов, подлежащих разбиению, целыми числами 1, 2, ..., n . Определите приведенные числа Стирлинга второго рода, обозначаемые , как количество способов разбить целые числа 1, 2, ..., n на k непустые подмножества так, что все элементы в каждом подмножестве имеют попарное расстояние не менее d . То есть для любых целых чисел i и j в данном подмножестве требуется, чтобы . Было показано, что эти числа удовлетворяют
(отсюда и название «редуцированный»). [18] Заметим (как по определению, так и по формуле приведения), что , знакомые числа Стирлинга второго рода.
^ Как ни странно, обозначения, которые комбинатористы используют для падающих факториалов, совпадают с обозначениями, используемыми в специальных функциях для возрастающих факториалов; см. символ Поххаммера .
^ Преобразование рядов с помощью варианта чисел Стирлинга, Имануэль Маркс, The American Mathematical Monthly 69 , № 6 (июнь – июль 1962 г.), стр. 530–532, JSTOR 2311194.
↑ Антонио Салмери, Introduzione alla teoria dei коэффициенты Fattoriali, Giornale di Matematiche di Battaglini 90 (1962), стр. 44–54.
^ Аб Кнут, DE (1992), «Два примечания к обозначениям», Amer. Математика. Ежемесячно , 99 (5): 403–422, arXiv : math/9205211 , Bibcode : 1992math......5211K, doi : 10.2307/2325085, JSTOR 2325085, S2CID 119584305
^ Н. М. Темме, Асимптотические оценки чисел Стирлинга, ИССЛЕДОВАНИЯ ПО ПРИКЛАДНОЙ МАТЕМАТИКЕ 89: 233-243 (1993), Elsevier Science Publishing.
^ Бродер, А. (1984). Числа г-Стирлинга. Дискретная математика 49, 241-259
^ Триана, Дж. (2022). r-числа Стирлинга второго рода через контекстно-свободные грамматики. Журнал автоматов, языков и комбинаторики 27(4), 323-333
^ Л. Конте, Продвинутая комбинаторика , Рейдель, 1974, с. 222.
^ А. Мор и Т.Д. Портер, Применения хроматических полиномов с участием чисел Стирлинга , Журнал комбинаторной математики и комбинаторных вычислений 70 (2009), 57–64.
Бояджиев, Христо (2012). «Близкие встречи с числами Стирлинга второго рода». Журнал «Математика» . 85 (4): 252–266. arXiv : 1806.09468 . дои : 10.4169/math.mag.85.4.252. S2CID 115176876..