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

Количество перестановок по циклам

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

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

Определения

Определение по алгебре

Знаковые числа Стерлинга первого рода являются коэффициентами в разложении падающего факториала ${\displaystyle s(n,k)}$

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

в степени переменной : ${\displaystyle x}$

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

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

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

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

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

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

Впоследствии было обнаружено, что абсолютные значения этих чисел равны числу перестановок определенных видов. Эти абсолютные значения, которые известны как беззнаковые числа Стирлинга первого рода, часто обозначаются или . Их можно определить непосредственно как число перестановок элементов с непересекающимися циклами . ^[1] ${\displaystyle |s(n,k)|}$ ${\displaystyle c(n,k)}$ ${\displaystyle \left[{n \atop k}\right]}$ ${\displaystyle n}$ ${\displaystyle k}$

Например, из перестановок трех элементов имеется одна перестановка с тремя циклами ( тождественная перестановка , заданная в однострочной записи как или в циклической записи как , три перестановки с двумя циклами ( , , и ) и две перестановки с одним циклом ( и ). Таким образом , , и . Можно видеть, что они согласуются с предыдущими алгебраическими вычислениями для . ${\displaystyle 3!=6}$ ${\displaystyle 123}$ ${\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}$

с(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).

Эти числа можно вычислить, рассматривая орбиты как классы сопряженности . Альфред Реньи заметил, что беззнаковое число Стирлинга первого рода также подсчитывает количество перестановок размера с максимумами слева направо. ^[3] ${\displaystyle \left[{n \atop k}\right]}$ ${\displaystyle n}$ ${\displaystyle k}$

Знаки

Знаки знаковых чисел Стирлинга первого рода зависят только от четности 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}$

для . ^[2] ${\displaystyle n>0}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Простые тождества

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

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

и

${\displaystyle \left[{0 \atop k}\right]=0}$если , или в более общем случае, если k > n . ${\displaystyle k>0}$ ${\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 {3n-1}{4}}{n \choose 3}\quad {\mbox{ and }}\quad \left[{n \atop n-3}\right]={n \choose 2}{n \choose 4}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Расширения для фиксированногок

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

$${\displaystyle \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. [ ^5] В этой форме простые тождества, приведенные выше, принимают вид

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

(Здесь δ — дельта-функция Кронекера , а — символ Похгаммера .) ^[6] ${\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 ^[7] ). ${\displaystyle [x^{k}]}$ ${\displaystyle x^{k}}$

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

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

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

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

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

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

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

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

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

Конкретные расширения предыдущего тождества приводят к следующим тождествам, расширяющим числа Стирлинга первого рода для первых нескольких малых значений : ${\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 здесь и здесь, соответственно. ^[11]

Сравнения

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

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

Где находится скобка Айверсона ? ${\displaystyle [b]}$

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

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

В более общем случае, для фиксированных целых чисел, если мы определим упорядоченные корни ${\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 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 }s(n,k){\frac {z^{n}}{n!}}={\frac {(\log(1+z))^{k}}{k!}}}$

и

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

Это тождество справедливо для формальных степенных рядов , и сумма сходится в комплексной плоскости при | z | < 1.

Другие тождества возникают при изменении порядка суммирования, взятии производных, выполнении замен z или u и т. д. Например, мы можем вывести: ^[14]

${\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 \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). ^{[15] [16]}

Асимптотика

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

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

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

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

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

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

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

Как обсуждалось ранее, по формулам Виета можно получить Число Стирлинга s(n,np) можно найти по формуле ^[18] $${\displaystyle \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}.}$$

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

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

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

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

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

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

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

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

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

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

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

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

${\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 n/2\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 n/2\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 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} представляет собой дельта-функцию Кронекера .

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

Обобщения

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

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

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

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

${\displaystyle {\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-гармоник , ^[21] ${\displaystyle F_{n}^{(r)}(t):=\sum _{k\leq n}t^{k}/f(k)^{r}}$

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

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

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

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

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

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

Ссылки

1. Wilf, Herbert S. (1990). Generatingfunctionology . Сан-Диего, Калифорния, США: Academic Press. стр. 73. ISBN 978-148324857-8.{{cite book}}: CS1 maint: date and year (link)
2. Knuth, Donald E. (1992). «Две заметки о нотации». American Mathematical Monthly . 99 (5): 403–422 – через JSTOR.
3. Реньи, Альфред (1962). «Теория элементов моряков сюиты наблюдений». Научные анналы Университета Клермона. Математика . Том 8 (2): 7–13.
4. См. разделы 6.2 и 6.5 книги «Конкретная математика» .
5. Ричард П. Стэнли , Перечислительная комбинаторика, том 1 (2-е изд.). Страница 34 онлайн-версии.
6. Адамчик, Виктор (1997). «О числах Стирлинга и суммах Эйлера». Журнал вычислительной и прикладной математики . 79 (1): 119–130. doi : 10.1016/S0377-0427(96)00167-7 . MR  1437973.
7. Флажоле и Седжвик (1995). «Преобразования Меллина и асимптотика: конечные разности и интегралы Райса» (PDF) . Теоретическая информатика . 144 (1–2): 101–124. doi :10.1016/0304-3975(94)00281-m.
8. Шмидт, доктор медицины (30 октября 2016 г.). «Преобразования функций генерации дзета-рядов, связанные с функциями полилогарифма и гармоническими числами k -го порядка». arXiv : 1610.09666 [math.CO].
9. Шмидт, доктор медицины (3 ноября 2016 г.). «Преобразования функций генерации дзета-рядов, связанные с обобщенными числами Стирлинга и частичными суммами дзета-функции Гурвица». arXiv : 1611.00957 [math.CO].
10. Таблица чисел Эйлера второго порядка и краткий обзор их свойств можно найти в разделе 6.2 Конкретной математики . Например, у нас есть, что . Эти числа также имеют следующую комбинаторную интерпретацию: если мы образуем все перестановки мультимножества со свойством, что все числа между двумя вхождениями больше, чем для , то — число таких перестановок, которые имеют подъемы. ${\displaystyle \sum _{k}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(2n-1)(2n-3)\cdots 1=(2n-1)!!}$ ${\displaystyle \{1,1,2,2,\ldots ,n,n\}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 1\leq k\leq n}$ ${\displaystyle \left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle }$ ${\displaystyle k}$
11. Шмидт, МД (2016). «Пакет компьютерной алгебры для распознавания полиномиальных последовательностей». arXiv : 1609.07301 [math.CO].
12. Герберт Вильф, Генерирующая функционалология, Раздел 4.6.
13. Шмидт, МД (2017). "Цепные дроби типа Якоби для обычных производящих функций обобщенных факториальных функций". J. Integer Seq . 20 (3). arXiv : 1610.09691 .
14. Я. В. Благушин (2016). «Два ряда разложений для логарифма гамма-функции, включающих числа Стирлинга и содержащих только рациональные коэффициенты для определенных аргументов, связанных с π ⁻¹ ». Журнал математического анализа и приложений . 442 (2): 404–434. arXiv : 1408.3902 . doi : 10.1016/j.jmaa.2016.04.032. S2CID  119661147.arXiv
15. Blagouchine, Iaroslav V. (2018). "Три заметки о представлениях Ser и Hasse для дзета-функций". INTEGERS: The Electronic Journal of Combinatorial Number Theory . 18A : 1–45. arXiv : 1606.02044 . Bibcode :2016arXiv160602044B.
16. См. также некоторые более интересные представления рядов и разложения, упомянутые в статье Коннона: Connon, DF (2007). "Некоторые ряды и интегралы, включающие дзета-функцию Римана, биномиальные коэффициенты и гармонические числа (Том I)". arXiv : 0710.4022 [math.HO]..
17. Эти оценки можно найти в разделе 26.8 Справочника по математическим функциям NIST .
18. Маленфант, Джером (2011). «Конечные выражения в замкнутой форме для функции распределения и чисел Эйлера, Бернулли и Стирлинга». arXiv : 1103.1585 [math.NT].
19. Комацу, Такао; Пита-Руис, Клаудио (2018). «Некоторые формулы для чисел Белла». Filomat . 32 (11): 3881–3889. doi : 10.2298/FIL1811881K . ISSN  0354-5180.
20. Я. В. Благушин (2016). «Разложения обобщенных констант Эйлера в ряды полиномов от π ⁻² и в формальные обволакивающие ряды только с рациональными коэффициентами». Журнал теории чисел . 158 (2): 365–396. doi :10.1016/j.jnt.2015.06.012.arXiv
21. Шмидт, Макси Д. (2016). «Комбинаторные тождества для обобщенных чисел Стирлинга, расширяющие -факториальные функции и -гармонические числа». arXiv : 1611.04708 [math.CO]. ${\displaystyle f}$ ${\displaystyle f}$
22. Шмидт, Макси Д. (2010). «Обобщенные j-факториальные функции, полиномы и приложения». J. Integer Seq . 13 .

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