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

разбиений 15 набора из 4 элементов, упорядоченных по диаграмме Хассе.

Имеется S (4,1), ..., S (4, 4) = 1, 7, 6, 1 разделов, содержащих 1, 2, 3, 4 множества.

В математике , особенно в комбинаторике , число Стирлинга второго рода (или число разбиения Стирлинга ) — это количество способов разбить набор из n объектов на k непустые подмножества и обозначается $S(n,k)$ или $\textstyle \left\{{n \atop k}\right\}$. Числа Стирлинга второго рода встречаются в области математики, называемой комбинаторикой , и изучении разбиений . Они названы в честь Джеймса Стирлинга .

Числа Стирлинга первого и второго рода можно понимать как обратные друг другу, если рассматривать их как треугольные матрицы . Данная статья посвящена особенностям чисел Стирлинга второго рода. Тождества, связывающие эти два вида, появляются в статье о числах Стирлинга .

Определение

Числа Стирлинга второго рода, записанные $S(n,k)$ или $\lbrace \textstyle {n \atop k}\rbrace$ с другими обозначениями подсчитайте количество разбить набор или способов $n$ помеченные предметы в $k$ непустые неразмеченные подмножества. Эквивалентно, они подсчитывают количество различных отношений эквивалентности с точностью до $k$ классы эквивалентности, которые могут быть определены на $n$ набор элементов. Фактически, существует биекция между множеством разбиений и множеством отношений эквивалентности на данном множестве. Очевидно,

$\left\{{n \atop n}\right\}=1$ для n ≥ 0 и $\left\{{n \atop 1}\right\}=1$ для n ≥ 1,

поскольку единственный способ разбить n -элементное множество на n частей — это поместить каждый элемент множества в свою часть, а единственный способ разбить непустое множество на одну часть — это поместить все элементы в одну и ту же часть. . В отличие от чисел Стирлинга первого рода , их можно вычислить по формуле одной суммы:

$\left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}i^{n}=\sum _{i=0}^{k}{\frac {(-1)^{k-i}i^{n}}{(k-i)!i!}}.$

Числа Стирлинга второго рода можно также охарактеризовать как числа, возникающие при выражении степеней неопределенного х через падающие факториалы.

$(x)_{n}=x(x-1)(x-2)\cdots (x-n+1).$

(В частности, ( x ) ₀ = 1, поскольку это пустой продукт .)

Другими словами

$\sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}.$

Обозначения

Для чисел Стирлинга второго рода использовались различные обозначения. Обозначение скобок ${\textstyle \textstyle \lbrace {n \atop k}\rbrace }$ использовался Имануэлем Марксом и Антонио Салмери в 1962 году для вариантов этих чисел. Это побудило Кнута использовать его, как показано здесь, в первом томе «Искусства компьютерного программирования» (1968). Согласно третьему изданию «Искусства компьютерного программирования» , это обозначение также использовалось ранее Йованом Караматой в 1935 году. Обозначение S ( n , k ) использовалось Ричардом Стэнли в его книге «Перечислительная комбинаторика» , а также, гораздо раньше, многими другими авторами.

Используемые на этой странице обозначения чисел Стирлинга не являются универсальными и могут противоречить обозначениям в других источниках.

с

Основная статья: Номер звонка

Поскольку число Стирлинга $\left\{{n \atop k}\right\}$ подсчитывает разбиения набора из n -элементов на k частей, сумма

$B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}$

по всем значениям k — общее количество разделов набора из n членов. Это число известно как n- е число Белла .

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

$a_{n}=\sum _{k=0}^{n}k!\left\{{n \atop k}\right\}.$

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

Ниже представлен треугольный массив значений чисел Стирлинга второго рода (последовательность A008277 в OEIS ):

к н	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.

Свойства

Рекуррентное отношение

Числа Стирлинга второго рода подчиняются рекуррентному соотношению

$\left\{{n+1 \atop k}\right\}=k\left\{{n \atop k}\right\}+\left\{{n \atop k-1}\right\}\quad {\mbox{for}}\;0<k<n$

с начальными условиями

$\left\{{n \atop n}\right\}=1\quad {\mbox{ for}}\;n\geq 0\quad {\text{ and }}\quad \left\{{n \atop 0}\right\}=\left\{{0 \atop n}\right\}=0\quad {\text{ for }}n>0{\text{.}}$

Например, число 25 в столбце k = 3 и строке n = 5 определяется как 25 = 7 + (3×6), где 7 — это число выше и слева от 25, 6 — это число выше 25 и 3. это столбец, содержащий 6.

Чтобы доказать эту повторяемость, заметим, что разбиение $n+1$ объекты на k непустые подмножества либо содержат $(n+1)$-ый объект как синглтон или нет. Количество способов, которыми синглтон является одним из подмножеств, определяется выражением

$\left\{{n \atop k-1}\right\}$

так как мы должны разделить оставшиеся n объектов на доступные $k-1$ подмножества. В другом случае $(n+1)$-th объект принадлежит подмножеству, содержащему другие объекты. Количество способов определяется выражением

$k\left\{{n \atop k}\right\}$

поскольку мы разделяем все объекты, кроме $(n+1)$-th на k подмножеств, и тогда у нас остается k вариантов вставки объекта $n+1$. Суммирование этих двух значений дает желаемый результат.

Другое рекуррентное соотношение имеет вид

$\left\lbrace {\begin{matrix}n\\k\end{matrix}}\right\rbrace ={\frac {k^{n}}{k!}}-\sum _{r=1}^{k-1}{\frac {\left\lbrace {\begin{matrix}n\\r\end{matrix}}\right\rbrace }{(k-r)!}}.$

что следует из оценки $\sum _{r=0}^{n}\left\{{n \atop r}\right\}(x)_{r}=x^{n}$ в $x=k$.

Простые личности

Некоторые простые тождества включают в себя

$\left\{{n \atop n-1}\right\}={\binom {n}{2}}.$

Это связано с тем, что разделение n элементов на n - 1 наборов обязательно означает разделение его на один набор размера 2 и n - 2 набора размера 1. Поэтому нам нужно выбрать только эти два элемента;

и

$\left\{{n \atop 2}\right\}=2^{n-1}-1.$

Чтобы увидеть это, сначала обратите внимание, что есть 2 ^н упорядоченные подмножеств A и B. пары дополнительных В одном случае A пусто, а в другом B пусто, поэтому 2 ^н − Остаются 2 упорядоченные пары подмножеств. Наконец, поскольку нам нужны неупорядоченные пары, а не упорядоченные , мы делим последнее число на 2, получая результат, указанный выше.

Другое явное расширение рекуррентного отношения дает тождества в духе приведенного выше примера.

Личности

Таблица в разделе 6.1 « Конкретной математики» содержит множество обобщенных форм конечных сумм, включающих числа Стирлинга. В число конкретных конечных сумм, имеющих отношение к этой статье, входят:

${\begin{aligned}\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}{n \choose j}\left\{{j \atop k}\right\}\\\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}(k+1)^{n-j}\left\{{j \atop k}\right\}\\\left\{{n+k+1 \atop k}\right\}&=\sum _{j=0}^{k}j\left\{{n+j \atop j}\right\}\\\left\{{n \atop \ell +m}\right\}{\binom {\ell +m}{\ell }}&=\sum _{k}\left\{{k \atop \ell }\right\}\left\{{n-k \atop m}\right\}{\binom {n}{k}}\end{aligned}}$

Явная формула

Числа Стирлинга второго рода задаются явной формулой:

$\left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}j^{n}=\sum _{j=0}^{k}{\frac {(-1)^{k-j}j^{n}}{(k-j)!j!}}.$

Это можно получить, используя исключение-включение для подсчета сюръекций от n до k и используя тот факт, что количество таких сюръекций равно ${\textstyle k!\left\{{n \atop k}\right\}}$.

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

$\Delta ^{k}x^{n}=\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}(x+j)^{n}.$

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

$B_{m}(0)=\sum _{k=0}^{m}{\frac {(-1)^{k}k!}{k+1}}\left\{{m \atop k}\right\}.$

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

$\left\{{n \atop k}\right\}=B_{n,k}(1,1,\dots ,1).$

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

$\left\{{n \atop k}\right\}=\sum _{\begin{array}{c}c_{1}+\ldots +c_{k}=n-k\\c_{1},\ldots ,\ c_{k}\ \geq \ 0\end{array}}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}$

Паритет

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

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

$\left\{{n \atop k}\right\}\equiv {\binom {z}{w}}\ {\pmod {2}},$ где $z=n-\left\lceil \displaystyle {\frac {k+1}{2}}\right\rceil ,\ w=\left\lfloor \displaystyle {\frac {k-1}{2}}\right\rfloor .$

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

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

${\begin{aligned}\mathbb {A} :\ \sum _{i\in \mathbb {A} }2^{i}&=n-k,\\\mathbb {B} :\ \sum _{j\in \mathbb {B} }2^{j}&=\left\lfloor {\dfrac {k-1}{2}}\right\rfloor .\\\end{aligned}}$

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

${\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2={\begin{cases}0,&\mathbb {A} \cap \mathbb {B} \neq \emptyset ;\\1,&\mathbb {A} \cap \mathbb {B} =\emptyset ;\end{cases}}$

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

${\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2:=\left[\left(\left(n-k\right)\ \And \ \left(\left(k-1\right)\,\mathrm {div} \,2\right)\right)=0\right];$

где $\left[b\right]$ это скобка Айверсона .

Четность центрального числа Стирлинга второго рода $\textstyle \left\{{2n \atop n}\right\}$ нечетно тогда и только тогда, когда $n$ — фиббинарное число , число, двоичное представление которого не имеет двух последовательных единиц.

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

Для фиксированного целого числа n обычная производящая функция чисел Стирлинга второго рода $\left\{{n \atop 0}\right\},\left\{{n \atop 1}\right\},\ldots$ дается

$\sum _{k=0}^{n}\left\{{n \atop k}\right\}x^{k}=T_{n}(x),$

где $T_{n}(x)$ являются полиномами Тушара . Если вместо этого суммировать числа Стирлинга с падающим факториалом, можно, среди прочего, показать следующие тождества:

$\sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}$

и

$\sum _{k=1}^{n+1}\left\{{n+1 \atop k}\right\}(x-1)_{k-1}=x^{n}$

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

$\sum _{k=0}^{n}\left\{{n \atop k}\right\}(n)_{k}=n^{n}$.

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

$\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}x^{n-k}=\prod _{r=1}^{k}{\frac {1}{1-rx}}={\frac {1}{x^{k+1}(1/x)_{k+1}}}$

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

$\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}={\frac {(e^{x}-1)^{k}}{k!}}.$

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

$\sum _{k=0}^{\infty }\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}y^{k}=e^{y(e^{x}-1)}.$

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

Если $n\geq 2$ и $1\leq k\leq n-1$, затем

${\frac {1}{2}}(k^{2}+k+2)k^{n-k-1}-1\leq \left\{{n \atop k}\right\}\leq {\frac {1}{2}}{n \choose k}k^{n-k}$

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

Для фиксированной стоимости $k,$ асимптотическое значение чисел Стирлинга второго рода как $n\rightarrow \infty$ дается

$\left\{{n \atop k}\right\}{\underset {n\to \infty }{\sim }}{\frac {k^{n}}{k!}}.$

Если $k=o({\sqrt {n}})$ (где o обозначает маленькое обозначение o ), тогда

$\left\{{n+k \atop n}\right\}{\underset {n\to \infty }{\sim }}{\frac {n^{2k}}{2^{k}k!}}.$

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

$\left\{{n \atop k}\right\}\sim {\sqrt {\frac {v-1}{v(1-G)}}}\left({\frac {v-1}{v-G}}\right)^{n-k}{\frac {k^{n}}{n^{k}}}e^{k(1-G)}\left({n \atop k}\right),$

где $v=n/k$, и $G\in (0,1)$ это уникальное решение $G=ve^{G-v}$. Относительная ошибка ограничена примерно $0.066/n$.

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

Для фиксированного $n$, $\left\{{n \atop k}\right\}$ имеет единственный максимум, который достигается не более чем для двух последовательных значений k . То есть существует целое число $k_{n}$ такой, что

$\left\{{n \atop 1}\right\}<\left\{{n \atop 2}\right\}<\cdots <\left\{{n \atop k_{n}}\right\}\geq \left\{{n \atop k_{n}+1}\right\}>\cdots >\left\{{n \atop n}\right\}.$

Глядя на таблицу значений выше, первые несколько значений для $k_{n}$ являются $0,1,1,2,2,3,3,4,4,4,5,\ldots$

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

$k_{n}{\underset {n\to \infty }{\sim }}{\frac {n}{\log n}},$

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

$\log \left\{{n \atop k_{n}}\right\}=n\log n-n\log \log n-n+O(n\log \log n/\log n).$

Приложения

Пуассона

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

$E(X^{n})=\sum _{k=0}^{n}\left\{{n \atop k}\right\}\lambda ^{k}.$

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

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

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

$E(X^{n})=\sum _{k=0}^{m}\left\{{n \atop k}\right\}.$

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

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

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

Числа Стирлинга второго рода могут представлять общее количество схем рифм для стихотворения из n строк. $S(n,k)$ дает количество возможных схем рифмования для n строк с использованием k уникальных рифмующихся слогов. Например, для стихотворения из 3 строк предусмотрена 1 схема рифмы с использованием всего одной рифмы (ааа), 3 схемы рифмы с использованием двух рифм (ааб, аба, абб) и 1 схема рифмы с использованием трех рифм (abc).

Варианты

r -числа Стирлинга второго рода

- число r Стирлинга второго рода $\left\{{n \atop k}\right\}_{r}$ подсчитывает количество разделов набора из n объектов на k непустые непересекающиеся подмножества, так что первые r элементов находятся в разных подмножествах. Эти числа удовлетворяют рекуррентному соотношению

$\left\{{n \atop k}\right\}_{r}=k\left\{{n-1 \atop k}\right\}_{r}+\left\{{n-1 \atop k-1}\right\}_{r}$

Некоторые комбинаторные тождества и связь между этими числами и контекстно-свободными грамматиками можно найти в

Ассоциированные числа Стирлинга второго рода

Число Стирлинга второго рода, связанное с r, — это количество способов разбить набор из n объектов на k подмножеств, каждое из которых содержит не менее r элементов. Это обозначается $S_{r}(n,k)$ и подчиняется рекуррентному соотношению

$S_{r}(n+1,k)=k\ S_{r}(n,k)+{\binom {n}{r-1}}S_{r}(n-r+1,k-1)$

2-ассоциированные числа (последовательность A008299 в OEIS ) появляются в других местах как «числа Уорда» и как величины коэффициентов полиномов Малера .

Стирлинга второго

Обозначим n объектов, подлежащих разбиению, целыми числами 1, 2, ..., n . Определим приведенные числа Стирлинга второго рода, обозначим $S^{d}(n,k)$, чтобы быть количеством способов разбить целые числа 1, 2, ..., n на k непустые подмножества так, чтобы все элементы в каждом подмножестве имели попарное расстояние не менее d . То есть для любых целых чисел i и j в заданном подмножестве требуется, чтобы $|i-j|\geq d$. Было показано, что эти числа удовлетворяют

$S^{d}(n,k)=S(n-d+1,k-d+1),n\geq k\geq d$

(отсюда и название «редуцированный»). Заметим (как по определению, так и по формуле приведения), что $S^{1}(n,k)=S(n,k)$, знакомые числа Стирлинга второго рода.

См. также

• Число Стирлинга
• Числа Стирлинга первого рода
• Номер колокола - количество разделов набора из n членов.
• Полиномы Стирлинга
• Двенадцатикратный путь
• Учебные материалы, связанные с числовыми треугольниками, связанными с разделами, в Викиверситете

Ссылки

• Бояджиев, Христо (2012). «Близкие встречи с числами Стирлинга второго рода». Журнал «Математика» . 85 (4): 252–266. arXiv : 1806.09468 . дои : 10.4169/math.mag.85.4.252 . S2CID   115176876 . .

• «Числа Стирлинга второго рода» . ПланетаМатематика . .
• Вайсштейн, Эрик В. «Число Стирлинга второго рода» . Математический мир .
• Калькулятор чисел Стирлинга второго рода
• Установить разделы: числа Стирлинга
• Джек ван дер Эльсен (2005). Черно-белые трансформации . Маастрихт. ISBN  90-423-0263-1 .