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

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

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

Определения

Числа Стирлинга первого рода являются коэффициентами $s(n,k)$ в разложении падающего факториала

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

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

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

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

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

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

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

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

Определение перестановкой

$\left[{n \atop k}\right]$ можно определить как количество перестановок на $n$ элементы с $k$ циклы.

с(4,2)=11

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

$(\bullet \bullet )(\bullet \bullet )$ (имея 2 орбиты, каждая размером 2),

и 8 перестановок формы

$(\bullet \bullet \bullet )(\bullet )$ (имея 1 орбиту размера 3 и 1 орбиту размера 1).

Эти числа можно вычислить, рассматривая орбиты как классы сопряжения (последний пункт).

Знаки

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

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

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

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

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

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

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

для $n>0$.

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

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

Алгебраическое доказательство

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

$x^{\overline {n+1}}=x(x+1)\cdots (x+n-1)(x+n)=n\cdot x^{\overline {n}}+x\cdot x^{\overline {n}}.$

Коэффициент $x^{k}$ в левой части этого уравнения есть $\left[{n+1 \atop k}\right]$. Коэффициент $x^{k}$ в $n\cdot x^{\overline {n}}$ является $n\cdot \left[{n \atop k}\right]$, а коэффициент $x^{k}$ в $x\cdot x^{\overline {n}}$ является $\left[{n \atop k-1}\right]$. Поскольку обе стороны равны как многочлены, коэффициенты $x^{k}$ с обеих сторон должны быть равны, и результат следует.

Комбинаторное доказательство

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

Рассмотрим формирование перестановки $n+1$ объекты из перестановки $n$ объекты путем добавления выделенного объекта. Есть ровно два способа, которыми это можно сделать. Мы могли бы сделать это, сформировав одноэлементный цикл, то есть оставив дополнительный объект в покое. Это увеличивает количество циклов на 1 и, таким образом, объясняет $\left[{n \atop k-1}\right]$ член рекуррентной формулы. Мы также могли бы вставить новый объект в один из существующих циклов. Рассмотрим произвольную перестановку $n$ объекты с $k$ циклы и маркируйте объекты $a_{1},\dots ,a_{n}$, так что перестановка представлена

$\displaystyle \underbrace {(a_{1}\ldots a_{j_{1}})(a_{j_{1}+1}\ldots a_{j_{2}})\ldots (a_{j_{k-1}+1}\ldots a_{n})} _{k\ \mathrm {cycles} }.$

Чтобы сформировать новую перестановку $n+1$ объекты и $k$ циклов необходимо вставить новый объект в этот массив. Есть $n$ способы выполнения этой вставки, вставляя новый объект сразу после любого из $a_{i}$ уже присутствует. Это объясняет $n\left[{n \atop k}\right]$ член рекуррентного отношения. Эти два случая включают в себя все возможности, поэтому следует рекуррентное соотношение.

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

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

к н	0	1	2	3	4	5	6	7	8	9	10
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1
9	0	40320	109584	118124	67284	22449	4536	546	36	1
10	0	362880	1026576	1172700	723680	269325	63273	9450	870	45	1

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

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

Используя дельту Кронекера , имеем:

$\left[{n \atop 0}\right]=\delta _{n}$

и

$\left[{0 \atop k}\right]=0$ если $k>0$или в более общем плане $\left[{n \atop k}\right]=0$ если к > п .

Также

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

и

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

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

Комбинаторные доказательства

Эти тождества могут быть получены путем непосредственного перечисления перестановок.Например, перестановка n элементов с n - 3 циклами должна иметь одну из следующих форм:

• n - 6 неподвижных точек и три двухцикла
• n - 5 фиксированных точек, трехтактный и двухтактный, или
• n − 4 неподвижных точки и четырехцикл.

Эти три типа можно перечислить следующим образом:

• выберем шесть элементов, входящих в двухциклы, разложим их на двухциклы и учтем, что порядок циклов неважен:

${n \choose 6}{6 \choose 2,2,2}{\frac {1}{6}}$

• выберем пять элементов, входящих в трехцикл и двуцикл, выберем элементы трехцикла и учтем, что три элемента порождают два трехцикла:

${n \choose 5}{5 \choose 3}\times 2$

• выберем четыре элемента четырехцикла и учтем, что четыре элемента порождают шесть четырехциклов:

${n \choose 4}\times 6.$

Суммируйте три вклада, чтобы получить

${n \choose 6}{6 \choose 2,2,2}{\frac {1}{6}}+{n \choose 5}{5 \choose 3}\times 2+{n \choose 4}\times 6={n \choose 2}{n \choose 4}.$

Обратите внимание, что во всех приведенных выше комбинаторных доказательствах используются либо биномы, либо мультиномы $n$.

Поэтому, если $p$ является простым, то:

$p\ |\left[{p \atop k}\right]$ для $1<k<p$.

Разложения для фиксированного k

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

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

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

$$\left[{\begin{matrix}n\\n-1\end{matrix}}\right]=\sum _{i=0}^{n-1}i={\binom {n}{2}},$$$$\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}},$$$$\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}},$$и так далее.

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

$(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),$

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

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

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

$\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}={\frac {1}{1}}+{\frac {1}{2}}+\ldots +{\frac {1}{n}}$ и Ч _н ^{( м )} - обобщенный номер гармоники $$H_{n}^{(m)}={\frac {1}{1^{m}}}+{\frac {1}{2^{m}}}+\ldots +{\frac {1}{n^{m}}}.$$

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

${\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 ) определяется рекурсивно через числа обобщенных гармоник формулой

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

(Здесь δ — дельта-функция Кронекера , $(m)_{k}$ является символом Поххаммера .)

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

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

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

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

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

$(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]$

$(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].$

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

$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).$

Конечные суммы

Поскольку перестановки делятся по количеству циклов, имеем

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

Личность

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

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

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

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

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

$\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(k+1)\left\langle \!\!\left\langle {n-1 \atop k}\right\rangle \!\!\right\rangle +(2n-1-k)\left\langle \!\!\left\langle {n-1 \atop k-1}\right\rangle \!\!\right\rangle ,$

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

$\left[{x \atop x-n}\right]=\sum _{k=0}^{n}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle {\binom {x+k}{2n}}.$

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

${\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 здесь и здесь соответственно.

Сравнения

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

${\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-фракции типа Якоби , которые генерируют единственную факториальную функцию и обобщенные продукты, связанные с факториалами, приводят к другим новым результатам сравнения для чисел Стирлинга первого рода. Например, работая по модулю $2$ мы можем доказать это

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

Где $[b]$ это скобка Айверсона .

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

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

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

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

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

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

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

$\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 цитированной выше ссылки приведены более явные расширения, связанные с этими сравнениями, для $r$-порядковые номера гармоник и для обобщенных факториалов , $p_{n}(\alpha ,R):=R(R+\alpha )\cdots (R+(n-1)\alpha )$.

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

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

$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).$

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

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

отсюда следует, что

$\sum _{n=k}^{\infty }s(n,k){\frac {z^{n}}{n!}}={\frac {(\log(1+z))^{k}}{k!}}$

и

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

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

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

или

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

и

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

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

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

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

$\zeta (s,v)={\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},\quad k=1,2,3,\ldots$

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

Асимптотика

Применима следующая оценка, данная через гамма-константу Эйлера :

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

Для фиксированного $n$ мы имеем следующую оценку:

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

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

Как известно, нам не известна ни одна формула одной суммы для чисел Стирлинга первого рода. Формулу двух сумм можно получить, используя одну из симметричных формул для чисел Стирлинга в сочетании с явной формулой для чисел Стирлинга второго рода .

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

Как обсуждалось ранее, по формулам Виеты можно получить $$\left[{\begin{matrix}n\\k\end{matrix}}\right]=\sum _{0\leq i_{1}<\ldots <i_{n-k}<n}i_{1}i_{2}\cdots i_{n-k}.$$Число Стирлинга s(n,np) можно найти по формуле

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

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

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

${\begin{aligned}\left[{n \atop k+1}\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}}$

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

Связь с функцией натурального логарифма

производная n я - й степени μ- натурального логарифма включает в себя знаковые числа Стирлинга первого рода:

${\operatorname {d} ^{n}\!(\ln x)^{\mu } \over \operatorname {d} \!x^{n}}=x^{-n}\sum _{k=1}^{n}\mu ^{\underline {k}}s(n,n-k+1)(\ln x)^{\mu -k},$

где $\mu ^{\underline {i}}$является падающим факториалом , и $s(n,n-k+1)$— число Стирлинга со знаком.

Это можно доказать с помощью математической индукции .

Другие формулы

Числа Стирлинга первого рода появляются в формуле для коэффициентов Грегори и в тождестве конечной суммы, включающем число Белла.

$n!G_{n}=\sum _{l=0}^{n}{\frac {s(n,l)}{l+1}}$

$\sum _{j=0}^{n}{\binom {n}{j}}B_{j}k^{n-j}=\sum _{i=0}^{k}\left[{k \atop i}\right]B_{n+i}(-1)^{k-i}$

Бесконечные ряды, включающие конечные суммы с числами Стирлинга, часто приводят к специальным функциям. Например

$\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 n/2\rfloor }\!{\frac {(-1)^{l}(2l)!}{(2\pi z)^{2l+1}}}\left[{n \atop 2l+1}\right]$

и

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

или даже

$\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 n/2\rfloor }{\frac {(-1)^{k}}{(2\pi )^{2k+1}}}\left[{2k+2 \atop m+1}\right]\left[{n \atop 2k+1}\right]\,$

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

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

Обобщения

Существует множество понятий обобщенных чисел Стирлинга , которые могут быть определены (в зависимости от применения) в различных комбинаторных контекстах. Поскольку числа Стирлинга первого рода соответствуют коэффициентам различных полиномиальных разложений одной факториальной функции , $n!=n(n-1)(n-2)\cdots 2\cdot 1$, мы можем расширить это понятие, чтобы определить треугольные рекуррентные отношения для более общих классов продуктов.

В частности, для любой фиксированной арифметической функции $f:\mathbb {N} \rightarrow \mathbb {C}$ и символические параметры $x,t$, связанные обобщенные факториалы вида

$(x)_{n,f,t}:=\prod _{k=1}^{n-1}\left(x+{\frac {f(k)}{t^{k}}}\right)$

могут быть изучены с точки зрения классов обобщенных чисел Стирлинга первого рода, определяемых следующими коэффициентами при степенях $x$ в расширениях $(x)_{n,f,t}$ а затем следующим соответствующим треугольным рекуррентным соотношением:

${\begin{aligned}\left[{\begin{matrix}n\\k\end{matrix}}\right]_{f,t}&=[x^{k-1}](x)_{n,f,t}\\&=f(n-1)t^{1-n}\left[{\begin{matrix}n-1\\k\end{matrix}}\right]_{f,t}+\left[{\begin{matrix}n-1\\k-1\end{matrix}}\right]_{f,t}+\delta _{n,0}\delta _{k,0}.\end{aligned}}$

Эти коэффициенты удовлетворяют ряду свойств, аналогичных свойствам чисел Стирлинга первого рода, а также рекуррентным соотношениям и функциональным уравнениям, связанным с -гармоническими числами f $F_{n}^{(r)}(t):=\sum _{k\leq n}t^{k}/f(k)^{r}$.

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

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

$\left|{\begin{matrix}n\\k\end{matrix}}\right|=(\alpha n+\beta k+\gamma )\left|{\begin{matrix}n-1\\k\end{matrix}}\right|+(\alpha ^{\prime }n+\beta ^{\prime }k+\gamma ^{\prime })\left|{\begin{matrix}n-1\\k-1\end{matrix}}\right|+\delta _{n,0}\delta _{k,0},$

для целых чисел $n,k\geq 0$ и где $\left|{\begin{matrix}n\\k\end{matrix}}\right|\equiv 0$ в любое время $n<0$ или $k<0$. В этом смысле форма чисел Стирлинга первого рода также может быть обобщена этой параметризованной суперрекуррентностью для фиксированных скаляров $\alpha ,\beta ,\gamma ,\alpha ^{\prime },\beta ^{\prime },\gamma ^{\prime }$ (не все ноль).

См. также

• Числа Стирлинга
• Числа Стирлинга второго рода
• Полиномы Стирлинга
• Статистика случайных перестановок

Ссылки

• Искусство компьютерного программирования
• Конкретная математика
• М. Абрамовиц, И. Стегун, изд. (1972). «§24.1.3. Числа Стирлинга первого рода». Справочник по математическим функциям с формулами, графиками и математическими таблицами (9-е изд.). Нью-Йорк: Дувр. п. 824.
• Числа Стирлинга первого рода, s(n,k) в PlanetMath ..
• Слоан, Нью-Джерси (ред.). «Последовательность A008275 (Треугольник читается рядами чисел Стирлинга первого рода)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.