stringtranslate.com

Числа Стирлинга второго рода

15 разбиений набора из 4 элементов, упорядоченных по диаграмме Хассе .
Имеется S (4,1), ..., S (4, 4) = 1, 7, 6, 1 разделов, содержащих 1, 2, 3, 4 множества.

В математике , особенно в комбинаторике , число Стирлинга второго рода (или число разбиения Стирлинга ) — это количество способов разделить набор из 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число Белла .

Аналогично упорядоченные числа Белла можно вычислить из чисел Стирлинга второго рода по формуле

[10]

Таблица значений

Ниже представлен треугольный массив значений чисел Стирлинга второго рода (последовательность 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 и используя тот факт, что количество таких сюръекций равно .

Кроме того, эта формула является частным случаем kпрямой разности монома, оцененного при x = 0:

Поскольку полиномы Бернулли можно записать через эти прямые разности, сразу получается соотношение чисел Бернулли :

Оценка неполного экспоненциального многочлена Белла B n , k ( x 1 , x 2 ,...) на последовательности единиц равна числу Стирлинга второго рода:

Другая явная формула, приведенная в Справочнике математических функций NIST :

Паритет

Четность чисел Стирлинга второго рода.

Четность числа Стирлинга второго рода равна четности соответствующего биномиального коэффициента :

где

Это отношение задается путем отображения координат n и k на треугольник Серпинского .

Более конкретно, пусть два набора содержат позиции единиц в двоичных представлениях результатов соответствующих выражений:

Можно имитировать побитовую операцию И , пересекая эти два набора:

получить четность числа Стирлинга второго рода за время O (1) . В псевдокоде :

где находится скобка Айверсона .

Четность центрального числа Стирлинга второго рода нечетна тогда и только тогда, когда является фиббинарным числом , числом, двоичное представление которого не имеет двух последовательных единиц. [11]

Генерирующие функции

Для фиксированного целого числа n обычная производящая функция для чисел Стирлинга второго рода имеет вид

где – полиномы Тушара . Если вместо этого суммировать числа Стирлинга с падающим факториалом, можно, среди прочего, показать следующие тождества:

и

Что имеет особый случай

.

Для фиксированного целого числа k числа Стирлинга второго рода имеют рациональную обычную производящую функцию

и имеют экспоненциальную производящую функцию, заданную выражением

Смешанная двумерная производящая функция для чисел Стирлинга второго рода:

Нижняя и верхняя границы

Если и , то

[12]

Асимптотическое приближение

При фиксированном значении асимптотического значения чисел Стирлинга второго рода, определяемого формулой

Если (где o обозначает маленькое обозначение o ), то

[13]

Также существует равномерно допустимое приближение: для всех k таких, что 1 < k < n , имеет место

где , и является единственным решением . [14] Относительная ошибка ограничена примерно .

Максимум для фиксированного n

При фиксированном имеет единственный максимум, который достигается не более чем для двух последовательных значений k . То есть существует целое число такое, что

Глядя на таблицу значений выше, первые несколько значений :

Когда большой

а максимальное значение числа Стирлинга можно аппроксимировать формулой

[12]

Приложения

Моменты распределения Пуассона

Если Xслучайная величина с распределением Пуассона с ожидаемым значением λ, то ее n- й момент равен

В частности, n- й момент распределения Пуассона с ожидаемым значением 1 — это в точности количество разбиений множества размера n , т. е. это nчисло Белла (этот факт и есть формула Добиньского ).

Моменты неподвижных точек случайных перестановок

Пусть случайная величина X — это количество неподвижных точек равномерно распределенной случайной перестановки конечного множества размера m . Тогда n- й момент X равен

Примечание. Верхняя граница суммирования равна m , а не n .

Другими словами, n- й момент этого распределения вероятностей — это количество разбиений множества размера n не более чем на m частей. Это доказано в статье о статистике случайных перестановок , хотя обозначения немного другие.

Схемы рифмований

Числа Стирлинга второго рода могут представлять общее количество схем рифм для стихотворения из 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] Заметим (как по определению, так и по формуле приведения), что , знакомые числа Стирлинга второго рода.

Смотрите также

Рекомендации

  1. ^ Рональд Л. Грэм, Дональд Э. Кнут, Орен Паташник (1988) Конкретная математика , Аддисон-Уэсли, Ридинг, Массачусетс. ISBN  0-201-14236-8 , с. 244.
  2. ^ «Числа Стирлинга второго рода, теорема 3.4.1».
  3. ^ Как ни странно, обозначения, которые комбинатористы используют для падающих факториалов, совпадают с обозначениями, используемыми в специальных функциях для возрастающих факториалов; см. символ Поххаммера .
  4. ^ Преобразование рядов с помощью варианта чисел Стирлинга, Имануэль Маркс, The American Mathematical Monthly 69 , № 6 (июнь – июль 1962 г.), стр. 530–532, JSTOR  2311194.
  5. Антонио Салмери, Introduzione alla teoria dei коэффициенты Fattoriali, Giornale di Matematiche di Battaglini 90 (1962), стр. 44–54.
  6. ^ Аб Кнут, DE (1992), «Два примечания к обозначениям», Amer. Математика. Ежемесячно , 99 (5): 403–422, arXiv : math/9205211 , Bibcode : 1992math......5211K, doi : 10.2307/2325085, JSTOR  2325085, S2CID  119584305
  7. ^ Дональд Э. Кнут, Фундаментальные алгоритмы , Ридинг, Массачусетс: Аддисон – Уэсли, 1968.
  8. ^ с. 66, Дональд Э. Кнут, Фундаментальные алгоритмы , 3-е изд., Ридинг, Массачусетс: Аддисон-Уэсли, 1997.
  9. ^ Джован Карамата, Теоремы о экспоненциальной соммабилити и других соммабилитах, Mathematica (Клуж) 9 (1935), стр, 164–178.
  10. ^ Спруньоли, Ренцо (1994), «Массивы Риордана и комбинаторные суммы» (PDF) , Discrete Mathematics , 132 (1–3): 267–290, doi : 10.1016/0012-365X(92)00570-H , MR  1297386
  11. ^ Чан, О-Йит; Манна, Данте (2010), «Сравнения для чисел Стирлинга второго рода» (PDF) , Gems in Experimental Mathematics , Contemporary Mathematics, vol. 517, Провиденс, Род-Айленд: Американское математическое общество, стр. 97–111, номер документа : 10.1090/conm/517/10135, MR  2731094.
  12. ^ аб Ренни, Британская Колумбия; Добсон, Эй Джей (1969). «О числах Стирлинга второго рода». Журнал комбинаторной теории . 7 (2): 116–121. дои : 10.1016/S0021-9800(69)80045-1 . ISSN  0021-9800.
  13. ^ LC Hsu , Примечание об асимптотическом разложении n-й разности нуля, AMS Vol.19 NO.2 1948, стр. 273–277
  14. ^ Н. М. Темме, Асимптотические оценки чисел Стирлинга, ИССЛЕДОВАНИЯ ПО ПРИКЛАДНОЙ МАТЕМАТИКЕ 89: 233-243 (1993), Elsevier Science Publishing.
  15. ^ Бродер, А. (1984). Числа г-Стирлинга. Дискретная математика 49, 241-259
  16. ^ Триана, Дж. (2022). r-числа Стирлинга второго рода через контекстно-свободные грамматики. Журнал автоматов, языков и комбинаторики 27(4), 323-333
  17. ^ Л. Конте, Продвинутая комбинаторика , Рейдель, 1974, с. 222.
  18. ^ А. Мор и Т.Д. Портер, Применения хроматических полиномов с участием чисел Стирлинга , Журнал комбинаторной математики и комбинаторных вычислений 70 (2009), 57–64.