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

В математике , особенно в комбинаторике , числа Стирлинга первого рода возникают при изучении перестановок. В частности, числа Стирлинга первого рода подсчитывают перестановки в соответствии с их количеством циклов (считая фиксированные точки как циклы длины один).

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

Определения [ править ]

Первоначальное определение чисел Стирлинга первого рода было алгебраическим: ^{[ цитата необходима ]} они являются коэффициентами s ( n ,  k ) в разложении падающего факториала

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

в степени переменной x :

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

Например, , что приводит к значениям , и .${\displaystyle (x)_{3}=x(x-1)(x-2)=1\cdot x^{3}-3\cdot x^{2}+2\cdot x}$${\displaystyle s(3,3)=1}$${\displaystyle s(3,2)=-3}$${\displaystyle s(3,1)=2}$

Впоследствии было обнаружено, что абсолютные значения | s ( n ,  k ) | из этих чисел равны количеству перестановок определенных видов. Эти абсолютные значения, известные как числа Стирлинга первого типа без знака, часто обозначаются символом или . Они могут быть определены непосредственно как число перестановок из п элементов с к непересекающихся циклов . Например, из перестановок трех элементов существует одна перестановка с тремя циклами ( тождественная перестановка , заданная в однострочном обозначении с помощью или в${\displaystyle c(n,k)}$${\displaystyle \left[{n \atop k}\right]}$${\displaystyle 3!=6}$${\displaystyle 123}$Цикл обозначения с ), три подстановки с двумя циклами ( , и ) и двух перестановок с одним циклом ( и ). Таким образом , и . Видно, что они согласуются с предыдущим вычислением for .${\displaystyle (1)(2)(3)}$${\displaystyle 132=(1)(23)}$${\displaystyle 213=(12)(3)}$${\displaystyle 321=(13)(2)}$${\displaystyle 312=(132)}$${\displaystyle 231=(123)}$${\displaystyle \left[{3 \atop 3}\right]=1}$${\displaystyle \left[{3 \atop 2}\right]=3}$${\displaystyle \left[{3 \atop 1}\right]=2}$${\displaystyle s(n,k)}$${\displaystyle n=3}$

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

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

Обозначения, используемые на этой странице для чисел Стирлинга, не являются универсальными и могут противоречить обозначениям в других источниках. (Обозначение квадратных скобок также является обычным обозначением для гауссовых коэффициентов .)${\displaystyle \left[{n \atop k}\right]}$

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

с (4,2) = 11

Изображение справа показывает, что : симметрическая группа на 4 объектах имеет 3 перестановки вида${\displaystyle \left[{4 \atop 2}\right]=11}$

${\displaystyle (\bullet \bullet )(\bullet \bullet )}$ (имеющий 2 орбиты, каждая размером 2),

и 8 перестановок вида

${\displaystyle (\bullet \bullet \bullet )(\bullet )}$ (имеющий 1 орбиту размера 3 и 1 орбиту размера 1).

Знаки [ править ]

Знаки (знаковых) чисел Стирлинга первого рода предсказуемы и зависят от четности n - k . Особенно,

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

Отношение повторения [ править ]

Беззнаковые числа Стирлинга первого рода можно вычислить с помощью рекуррентного соотношения

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

при , с начальными условиями${\displaystyle k>0}$

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

для n > 0.

Отсюда сразу следует, что числа Стирлинга первого рода (со знаком) удовлетворяют рекуррентности

${\displaystyle s(n+1,k)=-n\cdot s(n,k)+s(n,k-1)}$.

Таблица значений [ править ]

Ниже представлен треугольный массив беззнаковых значений для чисел Стирлинга первого типа, по форме похожий на треугольник Паскаля . Эти значения легко сгенерировать с помощью рекуррентного отношения из предыдущего раздела.

Свойства [ править ]

Простые личности [ править ]

Обратите внимание, что хотя

${\displaystyle \left[{0 \atop 0}\right]=1}$, имеем, если n > 0${\displaystyle \left[{n \atop 0}\right]=0}$

и

${\displaystyle \left[{0 \atop k}\right]=0}$если k > 0, или в более общем случае, если k > n .${\displaystyle \left[{n \atop k}\right]=0}$

Также

${\displaystyle \left[{n \atop 1}\right]=(n-1)!,\quad \left[{n \atop n}\right]=1,\quad \left[{n \atop n-1}\right]={n \choose 2},}$

и

${\displaystyle \left[{n \atop n-2}\right]={\frac {1}{4}}(3n-1){n \choose 3}\quad {\mbox{ and }}\quad \left[{n \atop n-3}\right]={n \choose 2}{n \choose 4}.}$

Аналогичные соотношения, включающие числа Стирлинга, имеют место и для полиномов Бернулли . Многие соотношения для чисел Стирлинга скрывают аналогичные соотношения для биномиальных коэффициентов . Изучение этих «теневых отношений» называется « теневым исчислением» и завершается теорией последовательностей Шеффера . Обобщения чисел Стирлинга обоих видов на произвольные комплексные входные данные могут быть расширены через отношения этих треугольников до полиномов свертки Стирлинга . ^[1]

Другие отношения [ править ]

Расширения для фиксированного k [ править ]

Поскольку числа Стирлинга являются коэффициенты полинома с корнями 0, 1, ..., п - 1 , один имеет по формулам Виета , что

$${\displaystyle \left[{\begin{matrix}n\\n-k\end{matrix}}\right]=\sum _{0\leq i_{1}<i_{2}<\ldots <i_{k}<n}i_{1}i_{2}\cdots i_{k}.}$$

Другими словами, числа Стирлинга первого рода задаются элементарными симметричными многочленами с оценками 0, 1, ..., n - 1 . ^[2] В этой форме приведенные выше простые тождества принимают вид

$${\displaystyle \left[{\begin{matrix}n\\n-1\end{matrix}}\right]=\sum _{i=0}^{n-1}i={\binom {n}{2}},}$$

$${\displaystyle \left[{\begin{matrix}n\\n-2\end{matrix}}\right]=\sum _{i=0}^{n-1}\sum _{j=0}^{i-1}ij={\frac {3n-1}{4}}{\binom {n}{3}},}$$

$${\displaystyle \left[{\begin{matrix}n\\n-3\end{matrix}}\right]=\sum _{i=0}^{n-1}\sum _{j=0}^{i-1}\sum _{k=0}^{j-1}ijk={\binom {n}{2}}{\binom {n}{4}},}$$

Можно получить альтернативные формы для чисел Стирлинга первого рода с помощью аналогичного подхода, которому предшествуют некоторые алгебраические манипуляции: поскольку

${\displaystyle (x+1)(x+2)\cdots (x+n-1)=(n-1)!\cdot (x+1)\left({\frac {x}{2}}+1\right)\cdots \left({\frac {x}{n-1}}+1\right),}$

из формул Ньютона следует , что числа Стирлинга первого рода можно разложить по обобщенным гармоническим числам . Это дает тождества вроде

${\displaystyle \left[{n \atop 2}\right]=(n-1)!\;H_{n-1},}$

${\displaystyle \left[{n \atop 3}\right]={\frac {1}{2}}(n-1)!\left[(H_{n-1})^{2}-H_{n-1}^{(2)}\right]}$

${\displaystyle \left[{n \atop 4}\right]={\frac {1}{3!}}(n-1)!\left[(H_{n-1})^{3}-3H_{n-1}H_{n-1}^{(2)}+2H_{n-1}^{(3)}\right],}$

где H _n - номер гармоники, а H _n ^{( m )} - обобщенный номер гармоники.${\displaystyle H_{n}={\frac {1}{1}}+{\frac {1}{2}}+\ldots +{\frac {1}{n}}}$

$${\displaystyle H_{n}^{(m)}={\frac {1}{1^{m}}}+{\frac {1}{2^{m}}}+\ldots +{\frac {1}{n^{m}}}.}$$

Эти отношения можно обобщить, чтобы дать

${\displaystyle {\frac {1}{(n-1)!}}\left[{\begin{matrix}n\\k+1\end{matrix}}\right]=\sum _{i_{1}=1}^{n-1}\sum _{i_{2}=i_{1}+1}^{n-1}\cdots \sum _{i_{k}=i_{k-1}+1}^{n-1}{\frac {1}{i_{1}i_{2}\cdots i_{k}}}={\frac {w(n,k)}{k!}}}$

где w ( n , m ) определяется рекурсивно через обобщенные гармонические числа как

${\displaystyle w(n,m)=\delta _{m,0}+\sum _{k=0}^{m-1}(1-m)_{k}H_{n-1}^{(k+1)}w(n,m-1-k).}$

(Здесь δ является дельта - функция Кронекера , и это символ похгаммера .) ^[3]${\displaystyle (m)_{k}}$

Для фиксированных значений эти взвешенные разложения гармонических чисел генерируются производящей функцией${\displaystyle n\geq 0}$

${\displaystyle {\frac {1}{n!}}\left[{\begin{matrix}n+1\\k\end{matrix}}\right]=[x^{k}]\exp \left(\sum _{m\geq 1}{\frac {(-1)^{m-1}H_{n}^{(m)}}{m}}x^{m}\right),}$

где обозначение означает извлечение коэффициента из следующего формального степенного ряда (см. неэкспоненциальные полиномы Белла и раздел 3 в ^[4] ).${\displaystyle [x^{k}]}$${\displaystyle x^{k}}$

В более общем смысле, суммы, относящиеся к этим взвешенным разложениям гармонических чисел для чисел Стирлинга первого рода, могут быть определены посредством преобразований в обобщенные дзета-ряды производящих функций . ^{[5] [6]}

Можно также «инвертировать» соотношения для этих чисел Стирлинга, заданные в терминах чисел гармоник -порядка, чтобы записать обобщенные гармонические числа целого порядка в терминах взвешенных сумм членов, содержащих числа Стирлинга первого рода. Например, когда числа гармоник второго и третьего порядка задаются выражением${\displaystyle k}$${\displaystyle k=2,3}$

${\displaystyle (n!)^{2}\cdot H_{n}^{(2)}=\left[{\begin{matrix}n+1\\2\end{matrix}}\right]^{2}-2\left[{\begin{matrix}n+1\\1\end{matrix}}\right]\left[{\begin{matrix}n+1\\3\end{matrix}}\right]}$

${\displaystyle (n!)^{3}\cdot H_{n}^{(3)}=\left[{\begin{matrix}n+1\\2\end{matrix}}\right]^{3}-3\left[{\begin{matrix}n+1\\1\end{matrix}}\right]\left[{\begin{matrix}n+1\\2\end{matrix}}\right]\left[{\begin{matrix}n+1\\3\end{matrix}}\right]+3\left[{\begin{matrix}n+1\\1\end{matrix}}\right]^{2}\left[{\begin{matrix}n+1\\4\end{matrix}}\right].}$

В более общем смысле, можно инвертировать производящую функцию полинома Белла для чисел Стирлинга, развернутых в терминах гармонических чисел -порядка, чтобы получить такую функцию для целых чисел${\displaystyle m}$${\displaystyle m\geq 2}$

${\displaystyle H_{n}^{(m)}=-m\times [x^{m}]\log \left(1+\sum _{k\geq 1}\left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]{\frac {(-x)^{k}}{n!}}\right).}$

Факторные суммы [ править ]

Для всех положительных целых m и n один имеет

$${\displaystyle (n+m)!=\sum _{k=0}^{n}\sum _{j=0}^{m}m^{\overline {n-k}}\left[{m \atop j}\right]{\binom {n}{k}}k!,}$$

где - возрастающий факториал. ^[7] Эта формула двойственна результату Спайви для чисел Белла . ^[7]${\displaystyle a^{\overline {b}}=a(a+1)\cdots (a+b-1)}$

Другие связанные формулы, включающие падающие факториалы, числа Стирлинга первого рода и, в некоторых случаях, числа Стирлинга второго рода, включают следующее: ^[8]

$${\displaystyle {\begin{aligned}n^{\underline {n-m}}&=\sum _{k}\left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]\left\{{\begin{matrix}k\\m\end{matrix}}\right\}(-1)^{m-k}\\{\binom {n}{m}}(n-1)^{\underline {n-m}}&=\sum _{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]\left\{{\begin{matrix}k\\m\end{matrix}}\right\}\\{\binom {n}{m}}&=\sum _{k}\left\{{\begin{matrix}n+1\\k+1\end{matrix}}\right\}\left[{\begin{matrix}k\\m\end{matrix}}\right](-1)^{m-k}\\\left[{\begin{matrix}n+1\\m+1\end{matrix}}\right]&=\sum _{0\leq k\leq n}\left[{\begin{matrix}k\\m\end{matrix}}\right]n^{\underline {n-k}}.\end{aligned}}}$$

Отношения инверсии и преобразование Стирлинга [ править ]

Для любой пары последовательностей и , связанных конечной суммой формулы числа Стирлинга, заданной формулой${\displaystyle \{f_{n}\}}$${\displaystyle \{g_{n}\}}$

${\displaystyle g_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}f_{k},}$

для всех целых чисел , у нас есть соответствующая формула обращения для данного${\displaystyle n\geq 0}$${\displaystyle f_{n}}$

${\displaystyle f_{n}=\sum _{k=1}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right](-1)^{n-k}g_{k}.}$

Эти отношения инверсии между двумя последовательностями переводятся в функциональные уравнения между экспоненциальными производящими функциями последовательности, заданными преобразованием Стирлинга (производящая функция) как

${\displaystyle {\widehat {G}}(z)={\widehat {F}}\left(e^{z}-1\right)}$

и

${\displaystyle {\widehat {F}}(z)={\widehat {G}}\left(\log(1+z)\right).}$

Эти дифференциальные операторы и связаны следующими формулами для всех целых чисел : ^[9]${\displaystyle D=d/dx}$${\displaystyle \vartheta =zD}$${\displaystyle n\geq 0}$

${\displaystyle \vartheta ^{n}=\sum _{k}S(n,k)z^{k}D^{k}}$

${\displaystyle z^{n}D^{n}=\sum _{k}s(n,k)\vartheta ^{k}}$

Другая пара соотношений « инверсии », включающая числа Стирлинга, связывает прямые разности и обычные производные функции , которая является аналитической для всех формулами ^[10]${\displaystyle n^{th}}$ ${\displaystyle f(x)}$${\displaystyle x}$

${\displaystyle {\frac {1}{k!}}{\frac {d^{k}}{dx^{k}}}f(x)=\sum _{n=k}^{\infty }{\frac {s(n,k)}{n!}}\Delta ^{n}f(x)}$

${\displaystyle {\frac {1}{k!}}\Delta ^{k}f(x)=\sum _{n=k}^{\infty }{\frac {S(n,k)}{n!}}{\frac {d^{n}}{dx^{n}}}f(x).}$

Конгруэнции [ править ]

Следующее тождество конгруэнции может быть доказано с помощью подхода, основанного на производящей функции : ^[11]

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\m\end{matrix}}\right]&\equiv {\binom {\lfloor n/2\rfloor }{m-\lceil n/2\rceil }}=[x^{m}]\left(x^{\lceil n/2\rceil }(x+1)^{\lfloor n/2\rfloor }\right)&&{\pmod {2}},\end{aligned}}}$

Более свежие результаты, дающие J-дроби типа Якоби, которые генерируют единственную факториальную функцию и обобщенные факториальные продукты, приводят к другим новым результатам сравнения для чисел Стирлинга первого рода. ^[12] Например, работая по модулю, мы можем доказать, что${\displaystyle 2}$

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\1\end{matrix}}\right]&\equiv {\frac {2^{n}}{4}}[n\geq 2]+[n=1]&&{\pmod {2}}\\\left[{\begin{matrix}n\\2\end{matrix}}\right]&\equiv {\frac {3\cdot 2^{n}}{16}}(n-1)[n\geq 3]+[n=2]&&{\pmod {2}}\\\left[{\begin{matrix}n\\3\end{matrix}}\right]&\equiv 2^{n-7}(9n-20)(n-1)[n\geq 4]+[n=3]&&{\pmod {2}}\\\left[{\begin{matrix}n\\4\end{matrix}}\right]&\equiv 2^{n-9}(3n-10)(3n-7)(n-1)[n\geq 5]+[n=4]&&{\pmod {2}}\\\left[{\begin{matrix}n\\5\end{matrix}}\right]&\equiv 2^{n-13}(27n^{3}-279n^{2}+934n-1008)(n-1)[n\geq 6]+[n=5]&&{\pmod {2}}\\\left[{\begin{matrix}n\\6\end{matrix}}\right]&\equiv {\frac {2^{n-15}}{5}}(9n^{2}-71n+120)(3n-14)(3n-11)(n-1)[n\geq 7]+[n=6]&&{\pmod {2}},\end{aligned}}}$

и работая по модулю, мы можем аналогично доказать, что${\displaystyle 3}$

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\1\end{matrix}}\right]&\equiv \sum \limits _{j=\pm 1}{\frac {1}{36}}\left(9-5j{\sqrt {3}}\right)\times \left(3+j{\sqrt {3}}\right)^{n}[n\geq 2]+[n=1]&&{\pmod {3}}\\\left[{\begin{matrix}n\\2\end{matrix}}\right]&\equiv \sum \limits _{j=\pm 1}{\frac {1}{216}}\left((44n-41)-(25n-24)\cdot j{\sqrt {3}}\right)\times \left(3+j{\sqrt {3}}\right)^{n}[n\geq 3]+[n=2]&&{\pmod {3}}\\\left[{\begin{matrix}n\\3\end{matrix}}\right]&\equiv \sum \limits _{j=\pm 1}{\frac {1}{15552}}\left((1299n^{2}-3837n+2412)-(745n^{2}-2217n+1418)\cdot j{\sqrt {3}}\right)\times \left(3+j{\sqrt {3}}\right)^{n}[n\geq 4]+[n=3]&&{\pmod {3}}\\\left[{\begin{matrix}n\\4\end{matrix}}\right]&\equiv \sum \limits _{j=\pm 1}{\frac {1}{179936}}{\bigl (}(6409n^{3}-383778n^{2}+70901n-37092)-(3690n^{3}-22374n^{2}+41088n-21708)\cdot j{\sqrt {3}}{\bigr )}\times \left(3+j{\sqrt {3}}\right)^{n}[n\geq 5]+[n=4]&&{\pmod {3}}.\end{aligned}}}$

В более общем смысле, для фиксированных целых чисел, если мы определим упорядоченные корни${\displaystyle h\geq 3}$

${\displaystyle \left(\omega _{h,i}\right)_{i=1}^{h-1}:=\left\{\omega _{j}:\sum _{i=0}^{h-1}{\binom {h-1}{i}}{\frac {h!}{(i+1)!}}(-\omega _{j})^{i}=0,\ 1\leq j<h\right\},}$

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

${\displaystyle \left[{\begin{matrix}n\\m\end{matrix}}\right]=[R^{m}]R(R+1)\cdots (R+n-1),}$

в следующем виде , где функция, , обозначает фиксированную полиномы степени в течение каждого , и :${\displaystyle p_{h,i}^{[m]}(n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle h}$${\displaystyle m}$${\displaystyle i}$

${\displaystyle \left[{\begin{matrix}n\\m\end{matrix}}\right]=\left(\sum _{i=0}^{h-1}p_{h,i}^{[m]}(n)\times \omega _{h,i}^{n}\right)[n>m]+[n=m]\qquad {\pmod {h}},}$

Раздел 6.2 ссылки упоминавшегося выше обеспечивает более явные разложения , связанные с этими сравнениями для -порядка гармонических чисел и для обобщенных факторных продуктов , . В предыдущих примерах обозначения обозначают соглашение Айверсона .${\displaystyle r}$${\displaystyle p_{n}(\alpha ,R):=R(R+\alpha )\cdots (R+(n-1)\alpha )}$${\displaystyle [{\mathtt {cond}}]}$

Генерация функций [ править ]

Множество тождеств можно получить, манипулируя производящей функцией :

${\displaystyle H(z,u)=(1+z)^{u}=\sum _{n=0}^{\infty }{u \choose n}z^{n}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}}\sum _{k=0}^{n}s(n,k)u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}s(n,k).}$

Используя равенство

${\displaystyle (1+z)^{u}=e^{u\log(1+z)}=\sum _{k=0}^{\infty }(\log(1+z))^{k}{\frac {u^{k}}{k!}},}$

следует, что

${\displaystyle \sum _{n=k}^{\infty }(-1)^{n-k}\left[{n \atop k}\right]{\frac {z^{n}}{n!}}={\frac {\left(\log(1+z)\right)^{k}}{k!}}.}$

(Это тождество справедливо для формальных степенных рядов , и сумма сходится в комплексной плоскости при | z | <1.) Другие тождества возникают при изменении порядка суммирования, взятии производных, замене z или u и т. Д. , мы можем получить: ^[13]

${\displaystyle (1-z)^{-u}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}\left[{n \atop k}\right]=e^{u\log(1/(1-z))}}$

и

${\displaystyle {\frac {\log ^{m}(1+z)}{1+z}}=m!\sum _{k=0}^{\infty }{\frac {s(k+1,m+1)\,z^{k}}{k!}},\qquad m=1,2,3,\ldots \quad |z|<1}$

или же

${\displaystyle \sum _{n=i}^{\infty }{\frac {\left[{n \atop i}\right]}{n\,(n!)}}=\zeta (i+1),\qquad i=1,2,3,\ldots }$

и

${\displaystyle \sum _{n=i}^{\infty }{\frac {\left[{n \atop i}\right]}{n\,(v)_{n}}}=\zeta (i+1,v),\qquad i=1,2,3,\ldots \quad \Re (v)>0}$

где и являются дзета - функция Римана , а функция Гурвица дзета соответственно, и даже оценить этот интеграл${\displaystyle \zeta (k)}$${\displaystyle \zeta (k,v)}$

${\displaystyle \int _{0}^{1}{\frac {\log ^{z}(1-x)}{x^{k}}}\,dx={\frac {(-1)^{z}\Gamma (z+1)}{(k-1)!}}\sum _{r=1}^{k-1}s(k-1,r)\sum _{m=0}^{r}{\binom {r}{m}}(k-2)^{r-m}\zeta (z+1-m),\qquad \Re (z)>k-1,\quad k=3,4,5,\ldots }$

где - гамма-функция . Существуют также более сложные выражения для дзета-функций, включающие числа Стирлинга. У одного, например, есть${\displaystyle \Gamma (z)}$

${\displaystyle {\frac {k!}{(s-k)_{k}}}\sum _{n=0}^{\infty }{\frac {1}{(n+k)!}}\left[{n+k \atop n}\right]\sum _{l=0}^{n+k-1}\!(-1)^{l}{\binom {n+k-1}{l}}(l+v)^{k-s}=\zeta (s,v),\quad k=1,2,3,\ldots }$

Этот ряд обобщает ряд Хассе для дзета-функции Гурвица (мы получаем ряд Хассе, полагая k = 1). ^{[14] [15]}

Асимптотика [ править ]

Применяется следующая оценка, представленная в терминах гамма-константы Эйлера : ^[16]

${\displaystyle \left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]\sim {\frac {n!}{k!}}\left(\gamma +\ln n\right)^{k},\ {\text{ uniformly for }}k=o(\ln n).}$

Для фиксированного мы имеем следующую оценку :${\displaystyle n}$${\displaystyle k\longrightarrow \infty }$

${\displaystyle \left[{\begin{matrix}n+k\\k\end{matrix}}\right]\sim {\frac {k^{2n}}{2^{n}n!}}.}$

Мы также можем применить асимптотические методы седловой точки из статьи Темме ^[17], чтобы получить другие оценки для чисел Стирлинга первого рода. Эти оценки сложнее сформулировать. Тем не менее, мы приводим пример. В частности, мы определяем логарифмическую гамма-функцию , производные высшего порядка которой задаются в терминах полигамма-функций как${\displaystyle \phi (x)}$

${\displaystyle {\begin{aligned}\phi (x)&=\ln \left[(1+1)(x+2)\cdots (x+n)\right]-m\ln x\\&=\ln \Gamma (x+n+1)-\ln \Gamma (x+1)-m\ln x\\\phi ^{\prime }(x)&=\psi (x+n+1)-\psi (x+1)-m/x,\end{aligned}}}$

где мы считаем (единственной) седловой точкой функции решение, когда . Тогда для и константы${\displaystyle x_{0}}$${\displaystyle \phi ^{\prime }(x)=0}$${\displaystyle 1\leq m\leq n}$${\displaystyle t_{0}=m/(n-m)}$

${\displaystyle B=\phi (x_{0})-n\ln(1+t_{0})+m\ln t_{0}}$

${\displaystyle g(t_{0})={\frac {1}{x_{0}}}{\sqrt {\frac {m(n-m)}{n\phi ^{\prime \prime }(x_{0})}}},}$

имеем следующую асимптотическую оценку как :${\displaystyle n\longrightarrow \infty }$

${\displaystyle \left[{\begin{matrix}n+1\\m+1\end{matrix}}\right]\sim e^{B}g(t_{0}){\binom {n}{m}}.}$

Конечные суммы [ править ]

Поскольку перестановки разбиваются по количеству циклов,

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

Личность

${\displaystyle \sum _{p=k}^{n}{\left[{n \atop p}\right]{\binom {p}{k}}}=\left[{n+1 \atop k+1}\right]}$

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

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

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\m\end{matrix}}\right]&=\sum _{k}\left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]{\binom {k}{m}}(-1)^{m-k}\\\left[{\begin{matrix}n+1\\m+1\end{matrix}}\right]&=\sum _{k=0}^{n}\left[{\begin{matrix}k\\m\end{matrix}}\right]{\frac {n!}{k!}}\\\left[{\begin{matrix}m+n+1\\m\end{matrix}}\right]&=\sum _{k=0}^{m}(n+k)\left[{\begin{matrix}n+k\\k\end{matrix}}\right]\\\left[{\begin{matrix}n\\l+m\end{matrix}}\right]{\binom {l+m}{l}}&=\sum _{k}\left[{\begin{matrix}k\\l\end{matrix}}\right]\left[{\begin{matrix}n-k\\m\end{matrix}}\right]{\binom {n}{k}}.\end{aligned}}}$

Другие тождества с конечной суммой, включающие подписанные числа Стирлинга первого типа, найденные, например, в Справочнике математических функций NIST (раздел 26.8), включают следующие суммы: ^[18]

${\displaystyle {\begin{aligned}{\binom {k}{h}}s(n,k)&=\sum _{j=k-h}^{n-h}{\binom {n}{j}}s(n-j,h)s(j,k-h)\\s(n+1,k+1)&=n!\times \sum _{j=k}^{n}{\frac {(-1)^{n-j}}{j!}}s(j,k)\\s(n,n-k)&=\sum _{j=0}^{k}(-1)^{j}{\binom {n-1+j}{k+j}}{\binom {n+k}{k-j}}S(k+j,j)\\s(n,k)&=\sum _{j=k}^{n}s(n+1,j+1)n^{j-k}.\end{aligned}}}$

Кроме того, если мы определим числа Эйлера второго порядка треугольным рекуррентным соотношением ^[19]

${\displaystyle E_{2}(n,k)=(k+1)E_{2}(n-1,k)+(2n-1-k)E_{2}(n-1,k-1)+\delta _{n,0}\delta _{k,0},}$

мы приходим к следующему тождеству, связанному с формой полиномов свертки Стирлинга, которые можно использовать для обобщения обоих треугольников чисел Стирлинга на произвольные действительные или комплексные значения входных данных :${\displaystyle x}$

${\displaystyle \left[{\begin{matrix}x\\x-n\end{matrix}}\right]=\sum _{k}E_{2}(n,k){\binom {x+k}{2n}}.}$

Конкретные расширения предыдущего тождества приводят к следующим тождествам, расширяющим числа Стирлинга первого рода для первых нескольких небольших значений :${\displaystyle n:=1,2,3}$

${\displaystyle {\begin{aligned}\left[{\begin{matrix}x\\x-1\end{matrix}}\right]&={\binom {x}{2}}\\\left[{\begin{matrix}x\\x-2\end{matrix}}\right]&={\binom {x}{4}}+2{\binom {x+1}{4}}\\\left[{\begin{matrix}x\\x-3\end{matrix}}\right]&={\binom {x}{6}}+8{\binom {x+1}{6}}+6{\binom {x+2}{6}}.\end{aligned}}}$

Программные средства для работы с конечными суммами с участием числа Стирлинга и числа эйлерова обеспечивается пакет RISC Stirling.m утилита в системе Mathematica . Другие пакеты программного обеспечения для угадывания формул для последовательностей (и сумм полиномиальных последовательностей), включающие числа Стирлинга и другие специальные треугольники, доступны как для Mathematica, так и для Sage здесь и здесь , соответственно. ^[20]

Более того, бесконечные ряды, включающие конечные суммы с числами Стирлинга, часто приводят к специальным функциям. Например ^{[13] [21]}

${\displaystyle \sum _{n=1}^{\infty }\!{\frac {(-1)^{n-1}}{n}}\cdot {\frac {1}{n!}}\sum _{l=1}^{n}\!{\frac {s(n,l)}{l+k}}=\sum _{l=2}^{\infty }\!{\frac {(-1)^{l}\cdot \zeta (l)}{l+k-1}}={\frac {1}{k-1}}-{\frac {\ln 2\pi }{k}}+{\frac {\gamma }{2}}+\!\!\!\!\sum _{l=1}^{\lfloor {\frac {1}{2}}(k-1)\rfloor }\!\!\!\!(-1)^{l}{\binom {k-1}{2l-1}}{\frac {(2l)!\cdot \zeta '(2l)}{l\cdot (2\pi )^{2l}}}+\!\!\sum _{l=1}^{\lfloor {\frac {1}{2}}k\rfloor -1}\!\!(-1)^{l}{\binom {k-1}{2l}}{\frac {(2l)!\cdot \zeta (2l+1)}{2\cdot (2\pi )^{2l}}}}$

или же

${\displaystyle \ln \Gamma (z)=\left(z-{\frac {1}{2}}\right)\!\ln z-z+{\frac {1}{2}}\ln 2\pi +{\frac {1}{\pi }}\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{l=0}^{\lfloor {\frac {1}{2}}n\rfloor }\!{\frac {(-1)^{l}(2l)!}{(2\pi z)^{2l+1}}}\left[{n \atop 2l+1}\right]}$

и

${\displaystyle \Psi (z)=\ln z-{\frac {1}{2z}}-{\frac {1}{\pi z}}\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{l=0}^{\lfloor {\frac {1}{2}}n\rfloor }\!{\frac {(-1)^{l}(2l+1)!}{(2\pi z)^{2l+1}}}\left[{n \atop 2l+1}\right]}$

или даже

${\displaystyle \gamma _{m}={\frac {1}{2}}\delta _{m,0}+{\frac {(-1)^{m}m!}{\pi }}\!\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{k=0}^{\lfloor {\frac {1}{2}}n\rfloor }{\frac {(-1)^{k}}{(2\pi )^{2k+1}}}\left[{2k+2 \atop m+1}\right]\left[{n \atop 2k+1}\right]\,}$

где γ _m - константы Стилтьеса, а δ _{m , 0} - дельта-функция Кронекера .

Явная формула [ править ]

Число Стирлинга s (n, np) можно найти по формуле ^[22]

${\displaystyle {\begin{aligned}s(n,n-p)&={\frac {1}{(n-p-1)!}}\sum _{0\leq k_{1},\ldots ,k_{p}:\sum _{1}^{p}mk_{m}=p}(-1)^{K}{\frac {(n+K-1)!}{k_{1}!k_{2}!\cdots k_{p}!~2!^{k_{1}}3!^{k_{2}}\cdots (p+1)!^{k_{p}}}},\end{aligned}}}$

где сумма представляет собой сумму по всем разделам на р .${\displaystyle K=k_{1}+\cdots +k_{p}.}$

Другое точное разложение вложенной суммы для этих чисел Стирлинга вычисляется с помощью элементарных симметричных многочленов, соответствующих коэффициентам в произведении формы . В частности, мы видим, что${\displaystyle x}$${\displaystyle (1+c_{1}x)\cdots (1+c_{n-1}x)}$

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\k+1\end{matrix}}\right]&=[x^{k}](x+1)(x+2)\cdots (x+n-1)=(n-1)!\cdot [x^{k}](x+1)\left({\frac {x}{2}}+1\right)\cdots \left({\frac {x}{n-1}}+1\right)\\&=\sum _{1\leq i_{1}<\cdots <i_{k}<n}{\frac {(n-1)!}{i_{1}\cdots i_{k}}}.\end{aligned}}}$

Тождества Ньютона в сочетании с приведенными выше разложениями могут использоваться для получения альтернативного доказательства взвешенных разложений, включающих уже отмеченные выше обобщенные числа гармоник .

Еще одна явная формула для взаимных полномочий по п дается следующее тождество для целых чисел : ^[23]${\displaystyle p\geq 2}$

${\displaystyle {\frac {1}{n^{p}}}={\frac {1}{n^{p-1}}}+{\frac {(-1)^{p-1}}{n!}}\left({\begin{bmatrix}n\\p\end{bmatrix}}+{\begin{bmatrix}n\\p-1\end{bmatrix}}\right)+{\frac {(-1)^{p}}{n\cdot n!}}{\begin{bmatrix}n+1\\p\end{bmatrix}}+\sum _{j=0}^{p-3}{\begin{bmatrix}n+1\\j+2\end{bmatrix}}{\frac {(-1)^{j+1}(n-1)}{n^{p-1-j}\cdot n!}}.}$