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

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

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

Обозначение [ править ]

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

${\ Displaystyle s (п, к) \,}$

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

${\ Displaystyle \ влево [{п \ на вершине к} \ вправо] = с (п, к) = | s (п, к) | = (- 1) ^ {nk} s (п, к) \,}$

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

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

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

Например, сумма - это количество всех перестановок, а сумма - это n- е число Белла .${\ 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}}$

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

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

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

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

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

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

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

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

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

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

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

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

и

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

Как изменение базисных коэффициентов [ править ]

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

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

это основа . То есть каждый многочлен от x может быть записан как сумма некоторых уникальных коэффициентов (аналогично для двух других оснований). Вышеупомянутые отношения затем выражают изменение базиса между ними, как показано на следующей коммутативной диаграмме :${\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},}$

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

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

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

Пример [ править ]

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

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

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

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

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

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

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

Номера Ла [ править ]

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

Числа могут быть определены как количество разделов n элементов на k непустых немаркированных подмножеств, каждое из которых неупорядочено, циклически упорядочено или линейно упорядочено соответственно. В частности, отсюда следуют следующие неравенства:${\displaystyle \textstyle {\begin{Bmatrix}n\\k\end{Bmatrix}},{\begin{bmatrix}n\\k\end{bmatrix}},L(n,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]}$

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

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

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

С другой стороны, для положительных целых чисел п и к , Дэвид Брансон ^[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 }$

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Адамчик, Виктор (1997). "О числах Стирлинга и суммах Эйлера" (PDF) . Журнал вычислительной и прикладной математики . 79 : 119–130. DOI : 10.1016 / s0377-0427 (96) 00167-7 .
• Бенджамин, Артур Т .; Престон, Грегори О .; Куинн, Дженнифер Дж. (2002). «Встреча Стирлинга с гармоническими числами» (PDF) . Математический журнал . 75 (2): 95–103. CiteSeerX  10.1.1.383.722 . DOI : 10.2307 / 3219141 . JSTOR  3219141 .
• Бояджиев, Христо Н. (2012). «Близкие встречи с числами Стирлинга второго рода» (PDF) . Математический журнал . 85 (4): 252–266. arXiv : 1806.09468 . DOI : 10.4169 / math.mag.85.4.252 .
• Контет, Луи (1970). "Valeur de s ( n ,  k ) " . Анализируйте Combinatoire, Tome Second (на французском языке): 51.
• Контет, Луи (1974). Продвинутая комбинаторика: искусство конечных и бесконечных расширений . Дордрехт-Голландия / Бостон-США: издательство Reidel Publishing Company.
• Сянь-Гуй Хван (1995). "Асимптотические разложения для чисел Стирлинга первого рода" . Журнал комбинаторной теории, Серия А . 71 (2): 343–351. DOI : 10.1016 / 0097-3165 (95) 90010-1 .
• Knuth, DE (1992), "Два примечания к обозначениям", Amer. Математика. Ежемесячно , 99 (5): 403–422, arXiv : math / 9205211 , doi : 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, JM; Пенсон, К.А.; Соломон, AI (2001). "Расширенные числа Белла и Стирлинга от гипергеометрического возведения в степень" (PDF) . Журнал целочисленных последовательностей . 4 : 01.1.4.
• Спайви, Майкл З. (2007). «Комбинаторные суммы и конечные разности». Дискретная математика . 307 (24). С. 3130–3146. DOI : 10.1016 / j.disc.2007.03.052 .
• Слоан, Н. Дж. А. (ред.). «Последовательность A008275 (числа Стирлинга первого рода)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
• Слоан, Н. Дж. А. (ред.). «Последовательность A008277 (числа Стирлинга 2-го рода)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.