Число Стирлинга - Stirling number - Wikipedia

В математика, Числа Стирлинга возникают в различных аналитический и комбинаторный проблемы. Они названы в честь Джеймс Стирлинг, который представил их в 18 веке. Это имя носят два разных набора чисел: Числа Стирлинга первого рода и Числа Стирлинга второго рода. Кроме того, Числа Ла иногда называют числами Стирлинга третьего рода. Каждый вид подробно описан в соответствующей статье, которая служит описанием отношений между ними.

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

Обозначение

Основная статья: Числа Стирлинга первого рода

Основная статья: Числа Стирлинга второго рода

Используются несколько различных обозначений чисел Стирлинга. Общие обозначения:

${\displaystyle \left[{n \atop k}\right]=c(n,k)=|s(n,k)|\,}$

для неподписанных Числа Стирлинга первого рода, которые подсчитывают количество перестановки из п элементы с k непересекающийся циклы,

${\displaystyle s(n,k)=(-1)^{n-k}\left[{n \atop k}\right]\,}$

для обыкновенных (знаковых) чисел Стирлинга первого рода и

${\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=S(n,k)=S_{n}^{(k)}\,}$

за Числа Стирлинга второго рода, которые подсчитывают количество способов разбить набор п элементы в k непустые подмножества.^[1]

Например, сумма ${\displaystyle \sum _{k=0}^{n}\left[{n \atop k}\right]=n!}$ - количество всех перестановок, а сумма ${\displaystyle \sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=B_{n}}$ это пth Номер звонка.

Абрамовиц и Стегун используйте заглавные буквы S и a чернокнижник S соответственно для первого и второго видов числа Стирлинга. Обозначение скобок и фигурных скобок, по аналогии с биномиальные коэффициенты, была представлена ​​в 1935 г. Йован Карамата и продвинутый позже Дональд Кнут. (Обозначение скобок противоречит общепринятому обозначению для Коэффициенты Гаусса.^[2]Математическое обоснование этого типа записи, а также дополнительные формулы чисел Стирлинга можно найти на странице для Числа Стирлинга и экспоненциальные производящие функции.

Расширения падающих и возрастающих факториалов

Числа Стирлинга выражают коэффициенты в разложениях падающие и восходящие факториалы (также известный как символ Поххаммера) в виде многочленов.

Это падающий факториал, определяется как ${\displaystyle (x)_{n}=x(x-1)\cdots (x-n+1)}$, является полиномом от Икс степени п чье расширение

${\displaystyle (x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k}}$

с числами Стирлинга первого рода (со знаком) в качестве коэффициентов.

Обратите внимание, что (Икс)₀ = 1, потому что это пустой продукт. Комбинатористы также иногда используют обозначения ${\displaystyle x^{\underline {n}}}$ для падающего факториала и ${\displaystyle x^{\overline {n}}}$ для растущего факториала.^[3] (Как ни странно, символ Поххаммера, который многие используют для падение факториалы используются в специальные функции за поднимающийся факториалы.)

Точно так же возрастающий факториал, определяется как ${\displaystyle x^{(n)}=x(x+1)\cdots (x+n-1)}$, является полиномом от Икс степени п чье расширение

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

с беззнаковыми числами Стирлинга первого рода в качестве коэффициентов. Одно разложение можно вывести из другого, заметив, что ${\displaystyle x^{(n)}=(-1)^{n}(-x)_{n}}$.

Числа Стирлинга второго рода выражают обратные отношения:

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

и

${\displaystyle x^{n}=\sum _{k=0}^{n}(-1)^{n-k}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}x^{(k)}.}$

Как изменение базисных коэффициентов

Учитывая набор многочлены в (неопределенной) переменной Икс как векторное пространство, каждая из трех последовательностей

${\displaystyle x^{0},x^{1},x^{2},x^{3},\cdots \quad (x)_{0},(x)_{1},(x)_{2},\cdots \quad x^{(0)},x^{(1)},x^{(2)},\cdots }$

это основа То есть каждый многочлен от Икс можно записать в виде суммы ${\displaystyle a_{0}x^{(0)}+a_{1}x^{(1)}+\dots +a_{n}x^{(n)}}$ для некоторых уникальных коэффициентов ${\displaystyle a_{i}}$ (аналогично для двух других баз). изменение основы между ними, как резюмируется в следующем коммутативная диаграмма:

Коэффициенты для двух изменений дна описываются Числа Ла Поскольку коэффициенты в любом базисе уникальны, можно определить числа Стирлинга таким образом, как коэффициенты, выражающие многочлены одного базиса через другой, то есть уникальные числа, связывающие ${\displaystyle x^{n}}$ с падающими и растущими факториалами, как указано выше.

Падающие факториалы определяют, с точностью до масштабирования, те же многочлены, что и биномиальные коэффициенты: ${\displaystyle \textstyle {\binom {x}{k}}={\frac {(x)_{k}}{k!}}}$. Изменения между стандартной базой ${\displaystyle \textstyle x^{0},x^{1},x^{2},\dots }$ и основа ${\displaystyle \textstyle {\binom {x}{0}},{\binom {x}{1}},{\binom {x}{2}},\dots }$ таким образом описываются аналогичными формулами:

${\displaystyle x^{n}=\sum _{k=0}^{n}{\begin{Bmatrix}n\\k\end{Bmatrix}}k!{\binom {x}{k}}}$ и ${\displaystyle {\binom {x}{n}}=\sum _{k=0}^{n}{\frac {s(n,k)}{n!}}x^{k}}$.

Как обратные матрицы

Числа Стирлинга первого и второго рода можно считать обратными друг другу:

${\displaystyle \sum _{j\geq 0}s(n,j)S(j,k)=\sum _{j\geq 0}(-1)^{n-j}{\begin{bmatrix}n\\j\end{bmatrix}}{\begin{Bmatrix}j\\k\end{Bmatrix}}=\delta _{nk}}$

и

${\displaystyle \sum _{j\geq 0}S(n,j)s(j,k)=\sum _{j\geq 0}(-1)^{j-k}{\begin{Bmatrix}n\\j\end{Bmatrix}}{\begin{bmatrix}j\\k\end{bmatrix}}=\delta _{nk},}$

куда ${\displaystyle \delta _{nk}}$ это Дельта Кронекера. Эти два отношения можно понимать как матричные обратные отношения. То есть пусть s быть нижняя треугольная матрица чисел Стирлинга первого рода, матричные элементы которых${\displaystyle s_{nk}=s(n,k).\,}$В обратный этой матрицы S, то нижняя треугольная матрица чисел Стирлинга второго рода, элементы которых ${\displaystyle S_{nk}=S(n,k).}$ Символически это написано

${\displaystyle s^{-1}=S\,}$

Несмотря на то что s и S бесконечны, поэтому при вычислении записи продукта требуется бесконечная сумма, умножение матриц работает, потому что эти матрицы имеют нижнюю треугольную форму, поэтому только конечное число членов в сумме не равно нулю.

Пример

Выражение полинома в основе падающих факториалов полезно для вычисления сумм полиномов, вычисленных в последовательных целых числах. Действительно, сумма падающего факториала просто выражается как другой падающий факториал (для к ≠ -1)

${\displaystyle \sum _{0\leq i<n}(i)_{k}={\frac {(n)_{k+1}}{k+1}}}$

Это аналог интеграла ${\displaystyle \textstyle \int _{0}^{n}x^{k}={\frac {n^{k+1}}{k+1}}}$, хотя сумма должна быть больше целых чисел я строго меньше чем п.

Например, сумма четвертых степеней целых чисел до п (на этот раз с п в комплекте), это:

${\displaystyle {\begin{aligned}&\sum _{i=0}^{n}i^{4}=\sum _{i=0}^{n}\sum _{k=0}^{4}{\begin{Bmatrix}4\\k\end{Bmatrix}}(i)_{k}=\sum _{k=0}^{4}{\begin{Bmatrix}4\\k\end{Bmatrix}}{\frac {(n+1)_{k+1}}{k+1}}=\\&={\frac {\{{\begin{smallmatrix}4\\1\end{smallmatrix}}\}}{2}}(n+1)_{2}+{\frac {\{{\begin{smallmatrix}4\\2\end{smallmatrix}}\}}{3}}(n+1)_{3}+{\frac {\{{\begin{smallmatrix}4\\3\end{smallmatrix}}\}}{4}}(n+1)_{4}+{\frac {\{{\begin{smallmatrix}4\\4\end{smallmatrix}}\}}{5}}(n+1)_{5}=\\&={\frac {1}{2}}(n+1)_{2}+{\frac {7}{3}}(n+1)_{3}+{\frac {6}{4}}(n+1)_{4}+{\frac {1}{5}}(n+1)_{5}\end{aligned}}}$

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

Напротив, сумма ${\displaystyle \sum _{i=0}^{n}i^{k}}$ в стандартном базисе Формула Фаульхабера, что в целом более сложно.

Числа Ла

Основная статья: Числа Ла

Числа Ла ${\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}}$ иногда называют числами Стирлинга третьего рода.^[4]Условно, ${\displaystyle L(0,0)=1}$ и ${\displaystyle L(n,k)=0}$ если ${\displaystyle n>k}$ или же ${\displaystyle k=0<n}$.

Эти числа представляют собой коэффициенты, выражающие падающие факториалы через возрастающие факториалы и наоборот:

${\displaystyle x^{(n)}=\sum _{k=0}^{n}L(n,k)(x)_{k}\quad }$ и ${\displaystyle \quad (x)_{n}=\sum _{k=0}^{n}(-1)^{n-k}L(n,k)x^{(k)}.}$

Как и выше, это означает, что они выражают изменение основы между основаниями. ${\displaystyle (x)_{0},(x)_{1},(x)_{2},\cdots }$ и ${\displaystyle x^{(0)},x^{(1)},x^{(2)},\cdots }$, завершая диаграмму. В частности, одна формула является обратной по отношению к другой, поэтому:

${\displaystyle \sum _{j}L(n,j)\cdot (-1)^{j-k}L(j,k)=\delta _{nk}.}$

Аналогично, составляя, например, изменение базы с ${\displaystyle x^{(n)}}$ к ${\displaystyle x^{n}}$ со сменой основы с ${\displaystyle x^{n}}$ к ${\displaystyle (x)_{n}}$ дает изменение базы прямо из ${\displaystyle x^{(n)}}$ к ${\displaystyle (x)_{n}}$:

${\displaystyle L(n,k)=\sum _{j}{\begin{bmatrix}n\\j\end{bmatrix}}{\begin{Bmatrix}j\\k\end{Bmatrix}},}$

В терминах матриц, если ${\displaystyle L}$ обозначает матрицу с элементами ${\displaystyle L_{nk}=L(n,k)}$ и ${\displaystyle L^{-}}$ обозначает матрицу с элементами ${\displaystyle L_{nk}^{-}=(-1)^{n-k}L(n,k)}$, то одно противоположно другому: ${\displaystyle L^{-}=L^{-1}}$Аналогично, составление матрицы беззнаковых чисел Стирлинга первого рода с матрицей чисел Стирлинга второго рода дает числа Лаха: ${\displaystyle L=|s|\cdot S}$.

Цифры ${\displaystyle \textstyle {\begin{Bmatrix}n\\k\end{Bmatrix}},{\begin{bmatrix}n\\k\end{bmatrix}},L(n,k)}$ можно определить как количество разделов п элементы в k непустые немаркированные подмножества, каждое из которых неупорядочено, циклически упорядоченный, или линейно упорядоченные соответственно. В частности, это влечет следующие неравенства:

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\leq {\begin{bmatrix}n\\k\end{bmatrix}}\leq L(n,k).}$

Симметричные формулы

Абрамовиц и Стегун приводят следующие симметричные формулы, связывающие числа Стирлинга первого и второго рода.^[5]

${\displaystyle s(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}S(n-k+j,j)}$

и

${\displaystyle S(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}s(n-k+j,j).}$

Числа Стирлинга с отрицательными целыми значениями

Числа Стирлинга можно расширить до отрицательных целых значений, но не все авторы делают это одинаково.^[6][7][8] Независимо от используемого подхода, стоит отметить, что числа Стирлинга первого и второго рода связаны соотношениями:

${\displaystyle \left[{n \atop k}\right]=\left\{{\begin{matrix}-k\\-n\end{matrix}}\right\}\,\qquad {\text{and}}\qquad \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left[{-k \atop -n}\right]}$

когда п и k неотрицательные целые числа. Итак, у нас есть следующая таблица для ${\displaystyle \left[{-n \atop -k}\right]}$:

k п	−1	−2	−3	−4	−5
−1	1	1	1	1	1
−2	0	1	3	7	15
−3	0	0	1	6	25
−4	0	0	0	1	10
−5	0	0	0	0	1

Дональд Кнут^[8] определили более общие числа Стирлинга, расширив отношение повторения ко всем целым числам. В этом подходе ${\displaystyle \left[{n \atop k}\right]}$ и ${\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}}$ равны нулю, если п отрицательный и k неотрицательно, или если п неотрицательно и k отрицательно, и поэтому мы имеем любой целые числа п и k,

${\displaystyle \left[{n \atop k}\right]=\left\{{\begin{matrix}-k\\-n\end{matrix}}\right\}\,\qquad {\text{and}}\qquad \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left[{-k \atop -n}\right]}$.

С другой стороны, для положительных целых чисел п и k, Дэвид Брэнсон^[7] определенный ${\displaystyle \left[{-n \atop -k}\right]}$, ${\displaystyle \left\{{\begin{matrix}-n\\-k\end{matrix}}\right\}}$, ${\displaystyle \left[{{-n} \atop k}\right]}$, и ${\displaystyle \left\{{\begin{matrix}-n\\k\end{matrix}}\right\}}$ (но нет ${\displaystyle \left[{n \atop -k}\right]}$ или же ${\displaystyle \left\{{\begin{matrix}n\\-k\end{matrix}}\right\}}$). В этом подходе имеется следующее расширение отношение повторения чисел Стирлинга первого рода:

${\displaystyle \left[{-n \atop k}\right]={\frac {(-1)^{n+1}}{n!}}\sum _{i=1}^{n}(-1)^{i+1}{\frac {n \choose i}{i^{k}}}}$,

Например, ${\displaystyle \left[{-5 \atop k}\right]={\frac {5-{\frac {10}{2^{k}}}+{\frac {10}{3^{k}}}-{\frac {5}{4^{k}}}+{\frac {1}{5^{k}}}}{120}}}$. Это приводит к следующей таблице значений ${\displaystyle \left[{-n \atop k}\right]}$.

k п	0	1	2	3	4
−1	1	1	1	1	1
−2	${\displaystyle {\tfrac {-1}{2}}}$	${\displaystyle {\tfrac {-3}{4}}}$	${\displaystyle {\tfrac {-7}{8}}}$	${\displaystyle {\tfrac {-15}{16}}}$	${\displaystyle {\tfrac {-31}{32}}}$
−3	${\displaystyle {\tfrac {1}{6}}}$	${\displaystyle {\tfrac {11}{36}}}$	${\displaystyle {\tfrac {85}{216}}}$	${\displaystyle {\tfrac {575}{1296}}}$	${\displaystyle {\tfrac {3661}{7776}}}$
−4	${\displaystyle {\tfrac {-1}{24}}}$	${\displaystyle {\tfrac {-25}{288}}}$	${\displaystyle {\tfrac {-415}{3456}}}$	${\displaystyle {\tfrac {-5845}{41472}}}$	${\displaystyle {\tfrac {-76111}{497664}}}$
−5	${\displaystyle {\tfrac {1}{120}}}$	${\displaystyle {\tfrac {137}{7200}}}$	${\displaystyle {\tfrac {12019}{432000}}}$	${\displaystyle {\tfrac {874853}{25920000}}}$	${\displaystyle {\tfrac {58067611}{1555200000}}}$

В этом случае ${\displaystyle \sum _{n=-1}^{-\infty }\left[{-n \atop -k}\right]=B_{k}}$ куда ${\displaystyle B_{k}}$ это Номер звонка, поэтому отрицательные числа Белла можно определить как ${\displaystyle \sum _{n=-1}^{-\infty }\left[{-n \atop k}\right]=B_{-k}}$. Например, это дает ${\displaystyle \sum _{n=-1}^{-\infty }\left[{-n \atop 2}\right]=B_{-2}=0.421773\ldots }$.

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

• Полиномы Белла
• Каталонский номер
• Циклы и фиксированные точки
• Номер Ла
• Символ Поххаммера
• Полиномиальная последовательность
• Преобразование Стирлинга
• Полиномы Тушара

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

1. Рональд Л. Грэм, Дональд Э. Кнут, Орен Паташник (1988) Конкретная математика, Аддисон-Уэсли, Ридинг, Массачусетс. ISBN  0-201-14236-8, п. 244.
2. Дональд Кнут
3. Айгнер, Мартин (2007). «Раздел 1.2 - Подмножества и биномиальные коэффициенты». Курс перечисления. Springer. стр.561. ISBN  978-3-540-39032-9.
4. Шандор, Йожеф; Crstici, Борислав (2004). Справочник по теории чисел II. Kluwer Academic Publishers. п. 464. ISBN  9781402025464.
5. Goldberg, K .; Ньюман, М; Хейнсворт, Э. (1972), «Числа Стирлинга первого вида, числа Стирлинга второго рода», в Абрамовиц, Милтон; Стегун, Ирен А. (ред.), Справочник по математическим функциям с формулами, графиками и математическими таблицами, 10-е издание, New York: Dover, pp. 824–825.
6. Лоеб, Дэниел Э. (1992) [Получено 3 ноября 1989 г.]. «Обобщение чисел Стирлинга». Дискретная математика. 103 (3): 259–269. Дои:10.1016 / 0012-365X (92) 90318-А.
7. Брэнсон, Дэвид (август 1994). «Расширение номеров Стирлинга» (PDF). Ежеквартальный отчет Фибоначчи. Получено 6 декабря, 2017.
8. D.E. Кнут, 1992.

дальнейшее чтение

• Адамчик, Виктор (1997). «О числах Стирлинга и суммах Эйлера» (PDF). Журнал вычислительной и прикладной математики. 79: 119–130. Дои:10.1016 / s0377-0427 (96) 00167-7.
• Бенджамин, Артур Т .; Престон, Грегори О .; Куинн, Дженнифер Дж. (2002). «Встреча Стирлинга с гармоническими числами» (PDF). Математический журнал. 75 (2): 95–103. CiteSeerX  10.1.1.383.722. Дои:10.2307/3219141. JSTOR  3219141.
• Бояджиев, Христо Н. (2012). «Близкие встречи с числами Стирлинга второго рода» (PDF). Математический журнал. 85 (4): 252–266. arXiv:1806.09468. Дои:10.4169 / math.mag.85.4.252.
• Контет, Луи (1970). "Валер де s(п, k)". Анализировать комбинаторику, Том второй (на французском языке): 51.
• Контет, Луи (1974). Продвинутая комбинаторика: искусство конечных и бесконечных расширений. Дордрехт-Голландия / Бостон-США: издательство Reidel Publishing Company.
• Сянь-Гуй Хван (1995). "Асимптотические разложения для чисел Стирлинга первого рода". Журнал комбинаторной теории, серия А. 71 (2): 343–351. Дои:10.1016/0097-3165(95)90010-1.
• Кнут, Д. (1992), «Два примечания по обозначениям», Амер. Математика. Ежемесячно, 99 (5): 403–422, arXiv:математика / 9205211, Дои:10.2307/2325085, JSTOR  2325085
• Микса, Фрэнсис Л. (январь 1956 г.). «Числа Стирлинга первого вида: 27 листов, воспроизведенных с машинописной рукописи, хранящейся в архиве UMT». Математические таблицы и другие вспомогательные средства для вычислений: обзоры и описания таблиц и книг. 10 (53): 37–38. JSTOR  2002617.
• Микса, Фрэнсис Л. (1972) [1964]. «Комбинаторный анализ, таблица 24.4, числа Стирлинга второго рода». В Абрамовиц, Милтон; Стегун, Ирен А. (ред.). Справочник по математическим функциям (с формулами, графиками и математическими таблицами). 55. Министерство торговли США, Национальное бюро стандартов, прикладная математика. п. 835.
• Митринович, Драгослав С. (1959). "Sur les nombres de Stirling de première espèce et les polynômes de Stirling" (PDF). Publications de la Faculté d'Electrotechnique de l'Université de Belgrade, Série Mathématiques et Physique (на французском) (23): 1–20. ISSN  0522-8441.
• О'Коннор, Джон Дж .; Робертсон, Эдмунд Ф. (сентябрь 1998 г.). "Джеймс Стирлинг (1692–1770)".
• Sixdeniers, J.M .; Пенсон, К. А .; Соломон, А. И. (2001). "Расширенные числа Белла и Стирлинга на основе гипергеометрического возведения в степень" (PDF). Журнал целочисленных последовательностей. 4: 01.1.4.
• Спайви, Майкл З. (2007). «Комбинаторные суммы и конечные разности». Дискретная математика. 307 (24). С. 3130–3146. Дои:10.1016 / j.disc.2007.03.052.
• Слоан, Н. Дж. А. (ред.). «Последовательность A008275 (числа Стирлинга первого рода)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
• Слоан, Н. Дж. А. (ред.). «Последовательность A008277 (числа Стирлинга 2-го рода)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
• «Числа Стирлинга первого рода, s (n, k)». PlanetMath.
• «Числа Стирлинга второго рода, S (n, k)». PlanetMath.