Числа Стирлинга второго рода - Stirling numbers of the second kind

В 15 перегородки из 4-х элементного комплекта заказываются в Диаграмма Хассе

Есть S(4,1), ..., S(4, 4) = 1, 7, 6, 1 разбиения, содержащие 1, 2, 3, 4 набора.

В математика, особенно в комбинаторика, а Число Стирлинга второго рода (или же Номер раздела Стирлинга) - количество способов разделить набор из п объекты в k непустые подмножества и обозначается ${\displaystyle S(n,k)}$ или же ${\displaystyle \textstyle \left\{{n \atop k}\right\}}$.^[1] Числа Стирлинга второго рода встречаются в области математика называется комбинаторика и изучение перегородки.

Числа Стирлинга второго типа - это один из двух видов Числа Стирлинга, другой вид называется Числа Стирлинга первого рода (или номера цикла Стирлинга). Взаимно обратный (конечный или бесконечный) треугольные матрицы могут быть сформированы из чисел Стирлинга каждого вида в соответствии с параметрами п, k.

Определение

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

${\displaystyle \left\{{n \atop n}\right\}=1}$ и для ${\displaystyle n\geq 1,\left\{{n \atop 1}\right\}=1}$

как единственный способ разбить п-элемент установлен в п Parts состоит в том, чтобы поместить каждый элемент набора в его собственную часть, и единственный способ разделить непустой набор на одну часть - поместить все элементы в одну и ту же часть. Их можно вычислить по следующей явной формуле:^[2]

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

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

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

(Особенно, (Икс)₀ = 1, потому что это пустой продукт.) В частности,

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

Обозначение

Для чисел Стирлинга второго рода использовались различные обозначения. Обозначение скобок ${\displaystyle \textstyle \lbrace {n \atop k}\rbrace }$ был использован Имануэлем Марксом и Антонио Салмери в 1962 году для вариантов этих чисел.^[4][5] Это привело Knuth использовать его, как показано здесь, в первом томе Искусство программирования (1968).^[6][7] Однако согласно третьему изданию Искусство программирования, это обозначение также использовалось ранее Йован Карамата в 1935 г.^[8][9] Обозначение S(п, k) использовался Ричард Стэнли в его книге Перечислительная комбинаторика.^[6]

Связь с номерами Bell

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

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

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

по всем значениям k - общее количество разделов набора с п члены. Это число известно как пth Номер звонка.

Аналогично заказанные номера Bell можно вычислить из чисел Стирлинга второго рода с помощью

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

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

Ниже приводится треугольная решетка значений чисел Стирлинга второго рода (последовательность 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 > п, но все эти записи будут 0.

Характеристики

Отношение рецидива

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

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

за k > 0 с начальными условиями

${\displaystyle \left\{{0 \atop 0}\right\}=1\quad {\mbox{ and }}\quad \left\{{n \atop 0}\right\}=\left\{{0 \atop n}\right\}=0}$

за п > 0.

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

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

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

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

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

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

Еще несколько рецидивов:

${\displaystyle \left\{{n+1 \atop k+1}\right\}=\sum _{j=k}^{n}{n \choose j}\left\{{j \atop k}\right\},}$

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

${\displaystyle \left\{{n+k+1 \atop k}\right\}=\sum _{j=0}^{k}j\left\{{n+j \atop j}\right\}.}$

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

Если ${\displaystyle n\geq 2}$ и ${\displaystyle 1\leq k\leq n-1}$, тогда

${\displaystyle L(n,k)\leq \left\{{n \atop k}\right\}\leq U(n,k)}$

куда

${\displaystyle L(n,k)={\frac {1}{2}}(k^{2}+k+2)k^{n-k-1}-1}$

и

${\displaystyle U(n,k)={\frac {1}{2}}{n \choose k}k^{n-k}.}$ ^[11]

Максимум

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

${\displaystyle \left\{{n \atop 1}\right\}<\left\{{n \atop 2}\right\}<\cdots <\left\{{n \atop K_{n}}\right\},}$

${\displaystyle \left\{{n \atop K_{n}}\right\}\geq \left\{{n \atop K_{n}+1}\right\}>\cdots >\left\{{n \atop n}\right\}.}$

Когда ${\displaystyle n}$ большой

${\displaystyle K_{n}\sim {\frac {n}{\log n}},}$

а максимальное значение числа Стирлинга второго рода равно

${\displaystyle \log \left\{{n \atop K_{n}}\right\}=n\log n-n\log \log n-n+O(n\log \log n/\log n).}$ ^[11]

Паритет

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

В паритет числа Стирлинга второго рода равно четности родственного биномиальный коэффициент:

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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];}$

куда ${\displaystyle \left[b\right]}$ это Кронштейн Айверсона.

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

Некоторые простые личности включают

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

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

и

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

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

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

${\displaystyle {\begin{aligned}\left\{{n \atop 2}\right\}&={\frac {{\frac {1}{1}}(2^{n-1}-1^{n-1})}{0!}}\\[8pt]\left\{{n \atop 3}\right\}&={\frac {{\frac {1}{1}}(3^{n-1}-2^{n-1})-{\frac {1}{2}}(3^{n-1}-1^{n-1})}{1!}}\\[8pt]\left\{{n \atop 4}\right\}&={\frac {{\frac {1}{1}}(4^{n-1}-3^{n-1})-{\frac {2}{2}}(4^{n-1}-2^{n-1})+{\frac {1}{3}}(4^{n-1}-1^{n-1})}{2!}}\\[8pt]\left\{{n \atop 5}\right\}&={\frac {{\frac {1}{1}}(5^{n-1}-4^{n-1})-{\frac {3}{2}}(5^{n-1}-3^{n-1})+{\frac {3}{3}}(5^{n-1}-2^{n-1})-{\frac {1}{4}}(5^{n-1}-1^{n-1})}{3!}}\\[8pt]&{}\ \ \vdots \end{aligned}}}$

Эти примеры можно резюмировать, повторяя

${\displaystyle \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)!}}.}$

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

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

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

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

Кроме того, эта формула является частным случаем kth форвардная разница из одночлен ${\displaystyle x^{n}}$ оценивается в Икс = 0:

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

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

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

Производящие функции

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

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

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

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

и

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

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

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

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

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

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

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

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

За фиксированное значение ${\displaystyle k,}$ асимптотическое значение чисел Стирлинга второго рода как ${\displaystyle n\rightarrow \infty }$ дан кем-то

${\displaystyle \left\{{n \atop k}\right\}\sim {\frac {k^{n}}{k!}}.}$

С другой стороны, если ${\displaystyle k=o({\sqrt {n}})}$ (куда о обозначает небольшое обозначение ) тогда

${\displaystyle \left\{{n \atop n-k}\right\}\sim {\frac {(n-k)^{2k}}{2^{k}k!}}\left(1+{\frac {1}{3}}{\frac {2k^{2}+k}{n-k}}+{\frac {1}{18}}{\frac {4k^{4}-k^{2}-3k}{(n-k)^{2}}}+\cdots \right).}$^[12]

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

${\displaystyle \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),}$

куда ${\displaystyle G=-W_{0}(-ve^{-v}),v=n/k}$, и ${\displaystyle W_{0}(z)}$ это основная ветвь W функция Ламберта.^[13] Относительная погрешность ограничена примерно ${\displaystyle 0.066/n}$.

Приложения

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

Если Икс это случайная переменная с распределение Пуассона с ожидаемое значение λ, то его пth момент является

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

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

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

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

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

Примечание: Верхняя граница суммирования равна м, нет п.

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

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

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

Варианты

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

An р-ассоциированное число Стирлинга второго рода - это количество способов разбиения множества п объекты в k подмножества, причем каждое подмножество содержит не менее р элементы.^[14] Обозначается он ${\displaystyle S_{r}(n,k)}$ и подчиняется рекуррентному соотношению

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

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

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

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

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

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

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

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

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

1. Рональд Л. Грэм, Дональд Э. Кнут, Орен Паташник (1988) Конкретная математика, Аддисон – Уэсли, Ридинг, Массачусетс. ISBN  0-201-14236-8, п. 244.
2. «Число Стирлинга второго рода».
3. Как ни странно, обозначения, которые комбинатористы используют для падение факториалов совпадает с обозначениями, используемыми в специальные функции за поднимающийся факториалы; видеть Символ Поххаммера.
4. Преобразование рядов по варианту чисел Стирлинга, Имануэль Маркс, Американский математический ежемесячник 69, № 6 (июнь – июль 1962 г.), стр. 530–532, JSTOR  2311194.
5. Антонио Салмери, «Введение в общую теорию коэффициентов жировых отложений», Математические площади Баттаглини 90 (1962), стр. 44–54.
6. Кнут, Д. (1992), «Два примечания по обозначениям», Амер. Математика. Ежемесячно, 99 (5): 403–422, arXiv:математика / 9205211, Bibcode:1992математика ...... 5211K, Дои:10.2307/2325085, JSTOR  2325085
7. Дональд Э. Кнут, Фундаментальные алгоритмы, Ридинг, Массачусетс: Аддисон – Уэсли, 1968.
8. п. 66, Дональд Э. Кнут, Фундаментальные алгоритмы, 3-е изд., Ридинг, Массачусетс: Addison – Wesley, 1997.
9. Йован Карамата, Теоремы о sommabilité exponentielle et d'autres sommabilités s'y rattachant, Mathematica (Клуж) 9 (1935), стр. 164–178.
10. Спругноли, Ренцо (1994), «Массивы Риордана и комбинаторные суммы» (PDF), Дискретная математика, 132 (1–3): 267–290, Дои:10.1016 / 0012-365X (92) 00570-H, МИСТЕР  1297386
11. Ренни, Британская Колумбия; Добсон, А.Дж. (1969). "О числах Стирлинга второго рода". Журнал комбинаторной теории. 7 (2): 116–121. Дои:10.1016 / S0021-9800 (69) 80045-1. ISSN  0021-9800.
12. Л. К. Сюй, Примечание об асимптотическом разложении n-й разности нуля, AMS Vol.19 NO.2 1948, pp. 273--277
13. Темме Н. М., Асимптотические оценки чисел Стирлинга, ИССЛЕДОВАНИЯ ПРИКЛАДНОЙ МАТЕМАТИКИ 89: 233-243 (1993), Elsevier Science Publishing.
14. Л. Контет, Продвинутая комбинаторика, Рейдель, 1974, стр. 222.
15. А. Мор и Т.Д. Портер, Приложения хроматических полиномов с числами Стирлинга, Журнал комбинаторной математики и комбинаторных вычислений 70 (2009), 57–64.

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

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