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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Означення[ред. | ред. код]

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

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

Наприклад,, що призводить до значень

Згодом було виявлено, що абсолютні значення цих чисел дорівнюють кількості перестановок елементної множини, які розкладаються в неперехресних циклів. Ці абсолютні значення, які відомі як беззнакові числа Стірлінга першого роду, часто позначаються  або .Наприклад, нехай . Така множина має перестановок. Найбільшу кількість циклів має  тотожна перестановка три цикли. Два цикли мають три перестановки: і один цикл мають та дві перестановки: Таким чином, , і . Можна побачити, що вони узгоджуються з попереднім розрахунком при .


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

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

Подальший приклад[ред. | ред. код]

Stirling number of the first kind s(4,2).svg

Зображення знизу доводить рівність : симетрична група на 4 об’єктах має 3 перестановки форми (має 2 орбіти, кожна розміром 2), і 8 перестановок форми (з 1 орбітою розміру 3 та 1 орбітою розміру 1).



Знаки[ред. | ред. код]

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

Рекурентне співвідношення[ред. | ред. код]

Беззнакові числа Стірлінга першого виду можна обчислити за відношенням рекурентності

при з початковими умовами i при . Звідси одразу випливає тотожність для знакових чисел Стірлінга першого роду:

Алгебричне доведення. Доведемо дане відношення рекурентності, використовуючи означення чисел Стірлінга з точки зору зростаючих факторіалів. Використавши означення , маємо

звідси

За означенням коефіцієнт при в лівій частині цієї рівності дорівнює В правій частині коефіцієнт при в доданку дорівнює , а в доданку відповідно дорівнює

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

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

Розглянемо утворення перестановок елементної множини з перестановок елементної множини приєднанням одного нового елемента. Це можна зробити двома способами. До кожної перестановки елементної множини поданої в циклічному виді, приєднаємо один цикл довжини один з новим елементом. Перестановки з циклами елементної множини утворюються з перестановок з циклами елементної множини, тому їх є . Інші перестановки отримаємо з перестановок елементної множини з  циклами приписуючи новий елемент до циклів які є після кожного з наявних елементів. Цим способом з кожної підстановки елементної множини отримаємо підстановок елементної множини, тому маємо  підстановок. Звідси випливає рекурентне співвідношення.

Таблиця значень[ред. | ред. код]

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

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

Властивості[ред. | ред. код]

Прості тотожності[ред. | ред. код]

Зауважте, що хоча

ми маємо якщо і якщо ,

або більш загально якщо

Також

,

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Література[ред. | ред. код]

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