Число Стірлінга першого роду

Вихідне визначення чисел Стірлінга першого роду було алгебричним вони є коефіцієнтами ${\displaystyle s(n,k)}$ при розкладі спадного факторіалу

${\displaystyle (x)_{n}=x(x-1)...(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)=1x^{3}-3x^{2}+2x}$, що призводить до значень ${\displaystyle s(3,3)=1,s(3,2)=-3,s(3,1)=2.}$

Згодом було виявлено, що абсолютні значення ${\displaystyle |s(n,k)|}$ цих чисел дорівнюють кількості перестановок ${\displaystyle n}$ елементної множини, які розкладаються в ${\displaystyle k}$ неперехресних циклів. Ці абсолютні значення, які відомі як беззнакові числа Стірлінга першого роду, часто позначаються ${\displaystyle c(n,k)}$ або ${\displaystyle {\binom {n}{k}}}$.Наприклад, нехай ${\displaystyle n=3}$. Така множина має ${\displaystyle 3!=6}$ перестановок. Найбільшу кількість циклів має  тотожна перестановка ${\displaystyle \iota =(1)(2)(3)}$ три цикли. Два цикли мають три перестановки: ${\displaystyle (1)(23),(2)(13),(3)(12)}$ і один цикл мають та дві перестановки: Таким чином, ${\displaystyle {\begin{bmatrix}3\\3\end{bmatrix}}=1}$, ${\displaystyle {\begin{bmatrix}3\\2\end{bmatrix}}=3}$ і ${\displaystyle {\begin{bmatrix}3\\1\end{bmatrix}}=2}$. Можна побачити, що вони узгоджуються з попереднім розрахунком ${\displaystyle s(n,k)}$ при ${\displaystyle n=3}$ .

Беззнакові числа Стірлінга також можуть бути визначені алгебрично як коефіцієнти зростаючого факторіалу :

${\displaystyle x^{\bar {n}}:=(x)^{n}:=x(x-1)...(x+n-1)=\textstyle \sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}\displaystyle }$

Позначення, що використовуються на цій сторінці для чисел Стірлінга, не є універсальними і можуть суперечити позначенням в інших джерелах. (Позначення квадратних дужок ${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}}$ також є загальним позначенням коефіцієнтів Гауса.)

Зображення знизу доводить рівність ${\displaystyle {\begin{bmatrix}4\\2\end{bmatrix}}=11}$: симетрична група на 4 об’єктах має 3 перестановки форми ${\displaystyle (\centerdot )(\centerdot )}$ (має 2 орбіти, кожна розміром 2), і 8 перестановок форми ${\displaystyle (\centerdot )(\centerdot \centerdot \centerdot )}$ (з 1 орбітою розміру 3 та 1 орбітою розміру 1).

Ознаки (знакових) чисел Стірлінга першого роду передбачувані і залежать від парності ${\displaystyle n-k}$. А саме, ${\displaystyle s(n,k)=(-1)^{n-k}}$

Беззнакові числа Стірлінга першого виду можна обчислити за відношенням рекурентності${\displaystyle {\begin{bmatrix}n+1\\k\end{bmatrix}}=n{\begin{bmatrix}n\\k\end{bmatrix}}+{\begin{bmatrix}n\\k-1\end{bmatrix}}}$

при ${\displaystyle k>0}$ з початковими умовами ${\displaystyle {\begin{bmatrix}0\\0\end{bmatrix}}:=0}$ i ${\displaystyle {\begin{bmatrix}n\\0\end{bmatrix}}:={\begin{bmatrix}0\\k\end{bmatrix}}:=0}$ при ${\displaystyle n>0}$. Звідси одразу випливає тотожність для знакових чисел Стірлінга першого роду: ${\displaystyle s(n+1,k)=-n\cdot s(n,k)+s(n,k-1)}$

Алгебричне доведення. Доведемо дане відношення рекурентності, використовуючи означення чисел Стірлінга з точки зору зростаючих факторіалів. Використавши означення ${\displaystyle x^{\bar {n}}}$, маємо

${\displaystyle x^{\bar {n+1}}=x(x+1)...(x+n-1)(x+n)=x^{\bar {n}}(n+x)}$

звідси ${\displaystyle x^{\bar {n+1}}=n\cdot x^{\bar {n}}+x\cdot x^{\bar {n}}}$

За означенням коефіцієнт при ${\displaystyle x^{k}}$ в лівій частині цієї рівності дорівнює ${\displaystyle {\begin{bmatrix}n+1\\k\end{bmatrix}}}$В правій частині коефіцієнт при ${\displaystyle x^{k}}$в доданку ${\displaystyle n\cdot x^{\bar {n}}}$ дорівнює ${\displaystyle n\cdot {\begin{bmatrix}n\\k\end{bmatrix}}}$, а в доданку ${\displaystyle x\cdot x^{\bar {n}}}$ відповідно дорівнює${\displaystyle {\begin{bmatrix}n\\k-1\end{bmatrix}}}$

З рівності многочленів випливає рівність коефіцієнтів при однакових степенях, тому виконується рекурентне співвідношення.

Комбінаторне доведення - доведемо рекурентне співвідношення, користуючись означенням чисел Стірлінга  через кількість циклів тобто, орбіт.

Розглянемо утворення перестановок ${\displaystyle n+1}$ елементної множини з перестановок ${\displaystyle n}$ елементної множини приєднанням одного нового елемента. Це можна зробити двома способами. До кожної перестановки ${\displaystyle n}$ елементної множини поданої в циклічному виді, приєднаємо один цикл довжини один з новим елементом. Перестановки з ${\displaystyle k}$ циклами ${\displaystyle n+1}$ елементної множини утворюються з перестановок з ${\displaystyle k-1}$ циклами ${\displaystyle n}$ елементної множини, тому їх є ${\displaystyle {\begin{bmatrix}n\\k-1\end{bmatrix}}}$ . Інші перестановки отримаємо ${\displaystyle n}$ з перестановок елементної множини з ${\displaystyle k}$ циклами приписуючи новий елемент до циклів які є після кожного з наявних елементів. Цим способом з кожної підстановки ${\displaystyle n}$ елементної множини отримаємо ${\displaystyle n}$ підстановок ${\displaystyle n+1}$ елементної множини, тому маємо ${\displaystyle n\cdot {\begin{bmatrix}n\\k\end{bmatrix}}}$ підстановок. Звідси випливає рекурентне співвідношення.

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

• Числа Стірлінга другого роду

• М.Й. Ядренко. Дискретна математика: навчальний посібник. - К.: МП"ТВіМС", 2004. - 245 с.