Число Стірлінга першого роду
В математиці , особливо в комбінаториці , числа Стерлінга першого роду виникають при вивченні перестановок. Зокрема, числа Стірлінга першого роду підраховують перестановки відповідно до їх кількості циклів (вважаючи нерухомі точки як цикли довжиною один).
Означення[ред. | ред. код]
Вихідне визначення чисел Стірлінга першого роду було алгебричним вони є коефіцієнтами при розкладі спадного факторіалу[en]
в степені змінної :
Наприклад,, що призводить до значень
Згодом було виявлено, що абсолютні значення цих чисел дорівнюють кількості перестановок елементної множини, які розкладаються в неперехресних циклів. Ці абсолютні значення, які відомі як беззнакові числа Стірлінга першого роду, часто позначаються або .Наприклад, нехай . Така множина має перестановок. Найбільшу кількість циклів має тотожна перестановка три цикли. Два цикли мають три перестановки: і один цикл мають та дві перестановки: Таким чином, , і . Можна побачити, що вони узгоджуються з попереднім розрахунком при .
Беззнакові числа Стірлінга також можуть бути визначені алгебрично як коефіцієнти зростаючого факторіалу[en] :
Позначення, що використовуються на цій сторінці для чисел Стірлінга, не є універсальними і можуть суперечити позначенням в інших джерелах. (Позначення квадратних дужок також є загальним позначенням коефіцієнтів Гауса.)
Подальший приклад[ред. | ред. код]
Зображення знизу доводить рівність : симетрична група на 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 | 225 | 85 | 15 | 1 | ||
7 | 0 | 720 | 1764 | 1624 | 735 | 175 | 21 | 1 | |
8 | 0 | 5040 | 13068 | 13132 | 6769 | 1960 | 322 | 28 | 1 |
Властивості[ред. | ред. код]
Прості тотожності[ред. | ред. код]
Зауважте, що хоча
ми маємо якщо і якщо ,
або більш загально якщо
Також
,
Подібні співвідношення за участю чисел Стірлінга мають місце і для многочленів Бернуллі . Багато співвідношень для чисел Стерлінга відтіняють подібні відношення на біноміальних коефіцієнтах . Вивчення цих "тіньових відношень" називається кам’яне числення[en] і завершується теорією послідовностей Шеффера[en] . Узагальнення чисел Стірлінга обох видів на довільні складні вхідні дані можуть бути розширені через відношення цих трикутників до поліномів згортки Стерлінга.
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
Література[ред. | ред. код]
- М.Й. Ядренко. Дискретна математика: навчальний посібник. - К.: МП"ТВіМС", 2004. - 245 с.