В математике , особенно в комбинаторике , число Стирлинга второго рода (или число разбиения Стирлинга ) представляет собой количество способов разбить набор из n объектов на k непустых подмножеств и обозначается как или же . [1] Числа Стирлинга второго типа встречаются в области математики, называемой комбинаторикой, и при изучении разбиений .
Числа Стирлинга второго типа - это один из двух видов чисел Стирлинга , другой вид которых называется числами Стирлинга первого типа (или числами цикла Стирлинга). Взаимно обратные (конечные или бесконечные) треугольные матрицы могут быть сформированы из чисел Стирлинга каждого вида в соответствии с параметрами n , k .
Определение
Числа Стирлинга второго рода, записанные или же или с другими обозначениями, подсчитать число способов разбить на набор из помеченные объекты в непустые немаркированные подмножества. Точно так же они подсчитывают количество различных отношений эквивалентности с точно классы эквивалентности, которые могут быть определены на набор элементов. Фактически, существует взаимно однозначное соответствие между множеством разбиений и множеством отношений эквивалентности на данном множестве. Очевидно,
- и для
поскольку единственный способ разделить набор n -элементов на n частей - это поместить каждый элемент набора в его собственную часть, а единственный способ разделить непустой набор на одну часть - это поместить все элементы в одну и ту же часть . Их можно рассчитать по следующей явной формуле: [2]
Числа Стирлинга второго рода также можно охарактеризовать как числа, возникающие при выражении степеней неопределенного x через падающие факториалы [3]
(В частности, ( x ) 0 = 1, потому что это пустой продукт .) В общем случае
Обозначение
Для чисел Стирлинга второго рода использовались различные обозначения. Обозначение скобокбыл использован Имануэлем Марксом и Антонио Салмери в 1962 году для вариантов этих чисел. [4] [5] Это побудило Кнута использовать его, как показано здесь, в первом томе «Искусство компьютерного программирования» (1968). [6] [7] Согласно третьему изданию «Искусства компьютерного программирования» , эта нотация также использовалась ранее Йованом Караматой в 1935 году. [8] [9] Нотация S ( n , k ) использовалась Ричардом Стэнли в его книгу « Перечислительная комбинаторика», а также, гораздо раньше, многими другими авторами. [6]
Обозначения, используемые на этой странице для чисел Стирлинга, не являются универсальными и могут противоречить обозначениям в других источниках.
Связь с номерами Bell
Поскольку число Стирлинга считает множество разбиений n -элементного набора на k частей, сумма
по всем значениям k - общее количество разбиений набора с n элементами. Это число известно как n- е число Белла .
Аналогично, упорядоченные числа Белла могут быть вычислены из чисел Стирлинга второго рода с помощью
Таблица значений
Ниже представлен треугольный массив значений чисел Стирлинга второго рода (последовательность A008277 в OEIS ):
k п | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | ||||||||||
1 | 0 | 1 | |||||||||
2 | 0 | 1 | 1 | ||||||||
3 | 0 | 1 | 3 | 1 | |||||||
4 | 0 | 1 | 7 | 6 | 1 | ||||||
5 | 0 | 1 | 15 | 25 | 10 | 1 | |||||
6 | 0 | 1 | 31 год | 90 | 65 | 15 | 1 | ||||
7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 год | 1 | |||
8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 год | 1 | ||
9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | |
10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 |
Как и в случае с биномиальными коэффициентами , эту таблицу можно расширить до k > n , но все эти записи будут равны 0.
Характеристики
Отношение повторения
Числа Стирлинга второго рода подчиняются рекуррентному соотношению
при k > 0 с начальными условиями
для n > 0.
Например, число 25 в столбце k = 3 и строке n = 5 задается как 25 = 7 + (3 × 6), где 7 - это число сверху и слева от 25, 6 - это число над 25 и 3. столбец, содержащий 6.
Чтобы доказать это повторение, заметим, что разбиение объектов в k непустых подмножеств либо содержит-й объект как синглтон или нет. Количество способов, которыми синглтон является одним из подмножеств, определяется выражением
так как мы должны разделить оставшиеся n объектов на доступныеподмножества. В другом случае-й объект принадлежит к подмножеству, содержащему другие объекты. Количество способов указано
поскольку мы разделяем все объекты, кроме -го на k подмножеств, и тогда у нас остается k вариантов для вставки объекта. Суммирование этих двух значений дает желаемый результат.
Еще несколько повторений:
Нижняя и верхняя границы
Если а также , тогда
где
а также
Максимум
Для фиксированных , имеет единственный максимум, который достигается не более чем при двух последовательных значениях k . То есть есть целое число такой, что
Когда большой
а максимальное значение числа Стирлинга второго рода равно
Паритет
Четности из числа Стирлинга второго рода равны четности связанного биномиального коэффициента :
- где
Это отношение задается отображением координат n и k на треугольник Серпинского .
Более конкретно, пусть два набора содержат позиции единиц в двоичных представлениях результатов соответствующих выражений:
Можно имитировать побитовую операцию И , пересекая эти два набора:
для получения четности числа Стирлинга второго рода за время O (1) . В псевдокоде :
где - скобка Айверсона .
Простые личности
Некоторые простые идентификаторы включают
Это потому, что разделение n элементов на n - 1 набор обязательно означает разделение его на один набор размером 2 и n - 2 набора размером 1. Следовательно, нам нужно выбрать только эти два элемента;
а также
Чтобы увидеть это, первую ноту , что существует 2 п упорядоченных пар комплементарных подмножеств A и B . В одном случае A пусто, а в другом B пусто, поэтому остаются 2 n - 2 упорядоченных пары подмножеств. Наконец, поскольку нам нужны неупорядоченные пары, а не упорядоченные пары, мы делим это последнее число на 2, получая результат выше.
Другое явное расширение отношения рекуррентности дает тождества в духе приведенного выше примера.
Эти примеры можно резюмировать повторением
Явная формула
Числа Стирлинга второго рода даются явной формулой:
Это можно получить, используя включение-исключение для подсчета количества сюрпризов от n до k и используя тот факт, что количество таких сюрпризов равно.
Кроме того, эта формула является частным случаем к - й прямой разности в одночлене оценивается при x = 0:
Поскольку полиномы Бернулли могут быть записаны в терминах этих прямых разностей, сразу получается соотношение в числах Бернулли :
Производящие функции
При фиксированном целочисленном п , в обычной производящей функции для чисел Стирлинга второго рода дан кем-то
где являются полиномами Тушара . Если вместо этого суммировать числа Стирлинга с падающим факториалом, можно показать, среди прочего, следующие тождества:
а также
Для фиксированного целого числа k числа Стирлинга второго рода имеют рациональную обыкновенную производящую функцию
и имеют экспоненциальную производящую функцию, заданную формулой
Смешанная двумерная производящая функция для чисел Стирлинга второго рода имеет вид
Асимптотическое приближение
При фиксированном значении асимптотическое значение чисел Стирлинга второго рода при дан кем-то
С другой стороны, если (где o обозначает маленькое обозначение o ), тогда
- [12]
Также существует равномерно допустимое приближение: для всех k таких, что 1 < k < n , выполняется
где , а также является главной ветвью W-функции Ламберта . [13] Относительная погрешность ограничена примерно.
Приложения
Моменты распределения Пуассона.
Если X - случайная величина с распределением Пуассона с математическим ожиданием λ, то ее n- й момент равен
В частности, n- й момент распределения Пуассона с математическим ожиданием 1 - это в точности количество разбиений множества размера n , т.е. это n- е число Белла (этот факт является формулой Добинского ).
Моменты неподвижных точек случайных перестановок
Пусть случайная величина X будет числом неподвижных точек равномерно распределенной случайной перестановки конечного множества размера m . Тогда n- й момент X равен
Примечание: верхняя граница суммирования равна m , а не n .
Другими словами, n- й момент этого распределения вероятностей - это количество разбиений набора размера n не более чем на m частей. Это доказано в статье о статистике случайных перестановок , хотя обозначения немного другие.
Схемы рифмования
Числа Стирлинга второго типа могут представлять общее количество схем рифм для стихотворения из n строк.дает количество возможных схем рифмования для n строк с использованием k уникальных рифмующихся слогов. Например, для стихотворения из 3 строк существует 1 схема рифмы с использованием только одной рифмы (aaa), 3 схемы рифмы с использованием двух рифм (aab, aba, abb) и 1 схема рифмы с использованием трех рифм (abc).
Варианты
Ассоциированные числа Стирлинга второго рода
Г -associated Стирлинг число второго рода является количеством способов разбиения набора п объектов на K подмножества, причем каждое подмножество , содержащем по крайней мере г элементы. [14] Обозначается и подчиняется рекуррентному соотношению
Два связанных числа (последовательность A008299 в OEIS ) появляются в другом месте как «числа Уорда» и как величины коэффициентов многочленов Малера .
Приведенные числа Стирлинга второго рода
Обозначим n объектов, которые нужно разделить, целыми числами 1, 2, ..., n . Определим приведенные числа Стирлинга второго рода, обозначенные, чтобы быть количеством способов разбить целые числа 1, 2, ..., n на k непустых подмножеств, так что все элементы в каждом подмножестве имеют попарное расстояние не менее d . То есть для любых целых чисел i и j в данном подмножестве требуется, чтобы. Было показано, что эти числа удовлетворяют
(отсюда и название «редуцированный»). [15] Заметим (как по определению, так и по формуле приведения), что, знакомые числа Стирлинга второго рода.
Смотрите также
- Bell number - количество разделов набора с n членами
- Числа Стирлинга первого рода
- Полиномы Стирлинга
- Двенадцатикратный путь
- Учебные материалы по числовым треугольникам, связанным с разделами, в Викиверситете
Рекомендации
- ^ Рональд Л. Грэм, Дональд Э. Кнут, Орен Паташник (1988) Конкретная математика , Аддисон-Уэсли, Ридинг, Массачусетс. ISBN 0-201-14236-8 , стр. 244.
- ^ «Второе число Стирлинга» .
- ^ Заблуждение, что обозначение, которое комбинатористы используют для падающих факториалов, совпадает с обозначением, используемым в специальных функциях для возрастающих факториалов; см. символ Почхаммера .
- ^ Преобразование рядов с помощью варианта чисел Стирлинга, Имануэль Маркс, The American Mathematical Monthly 69 , № 6 (июнь – июль 1962 г.), стр. 530–532, JSTOR 2311194 .
- ^ Антонио Salmeri, Introduzione алла Teoria дей coefficienti fattoriali, Giornale ди Matematiche ди Battaglini 90 (1962), стр. 44-54.
- ^ а б Knuth, DE (1992), "Два примечания к обозначениям", Amer. Математика. Ежемесячно , 99 (5): 403–422, arXiv : math / 9205211 , Bibcode : 1992math ...... 5211K , doi : 10.2307 / 2325085 , JSTOR 2325085
- ^ Дональд Э. Кнут, Фундаментальные алгоритмы , чтение, Массачусетс: Аддисон-Уэсли, 1968.
- ^ стр. 66, Дональд Э. Кнут, Фундаментальные алгоритмы , 3-е изд., Рединг, Массачусетс: Аддисон – Уэсли, 1997.
- ^ Йован Карамат, Théorèm сюр ли sommabilité exponentielle и d'Autres sommabilités протезы толкует rattachant, Mathematica (Cluj) 9 (1935), стр, 164-178.
- ^ Sprugnoli, Ренцо (1994), "массивы Риордан и комбинаторные суммы" (PDF) , дискретная математика , 132 (1-3): 267-290, DOI : 10.1016 / 0012-365X (92) 00570-Н , МР 1297386
- ^ а б Ренни, Британская Колумбия; Добсон, AJ (1969). «О числах Стирлинга второго рода» . Журнал комбинаторной теории . 7 (2): 116–121. DOI : 10.1016 / S0021-9800 (69) 80045-1 . ISSN 0021-9800 .
- ↑ LC Hsu , Note on an asymptotic Expansion nth Difference of Zero, AMS Vol.19 NO.2 1948, pp. 273--277.
- ^ NM Temme, Асимптотические оценки чисел Стирлинга, ИССЛЕДОВАНИЯ ПРИКЛАДНОЙ МАТЕМАТИКИ 89: 233-243 (1993), Elsevier Science Publishing.
- ^ L. Комте, Advanced Комбинаторика , Reidel, 1974, стр. 222.
- ^ А. Мор и Т.Д. Портер, Приложения хроматических многочленов, включающие числа Стирлинга , Журнал комбинаторной математики и комбинаторных вычислений 70 (2009), 57–64.
- Бояджиев, Христо (2012). «Близкие встречи с числами Стирлинга второго рода». Математический журнал . 85 (4): 252–266. arXiv : 1806.09468 . DOI : 10.4169 / math.mag.85.4.252 ..
- «Числа Стирлинга второго рода, S (n, k)» . PlanetMath ..
- Вайсштейн, Эрик В. "Число Стирлинга второго рода" . MathWorld .
- Калькулятор чисел Стирлинга второго рода
- Установить перегородки: числа Стирлинга
- Джек ван дер Эльсен (2005). Черно-белые трансформации . Маастрихт. ISBN 90-423-0263-1.