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

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

Означення

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

$(x)_{n}=x(x-1)...(x-n+1).$

в степені змінної $x$:

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

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

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

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

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

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

Подальший приклад

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

Знаки

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

Рекурентне співвідношення

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

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

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

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

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

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

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

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

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

Таблиця значень

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

n \ k	0	1	2	3	4	5	6	7	8
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	255	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1

Властивості

Прості тотожності

Зауважте, що хоча ${\begin{bmatrix}0\\0\end{bmatrix}}=1$

ми маємо ${\begin{bmatrix}n\\0\end{bmatrix}}$ якщо $n>0$ і ${\begin{bmatrix}0\\k\end{bmatrix}}=0$ якщо $k>0$ ,

або більш загально ${\begin{bmatrix}n\\k\end{bmatrix}}=0$ якщо $k>n$

Також

${\begin{bmatrix}n\\1\end{bmatrix}}=(n-1)!$, ${\begin{bmatrix}n\\n\end{bmatrix}}=1$

Подібні співвідношення за участю чисел Стірлінга мають місце і для многочленів Бернуллі . Багато співвідношень для чисел Стерлінга відтіняють подібні відношення на біноміальних коефіцієнтах . Вивчення цих "тіньових відношень" називається кам’яне числення і завершується теорією послідовностей Шеффера . Узагальнення чисел Стірлінга обох видів на довільні складні вхідні дані можуть бути розширені через відношення цих трикутників до поліномів згортки Стерлінга.

Див. також

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

Література

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