В математиці , особливо в комбінаториці , числа Стерлінга першого роду виникають при вивченні перестановок. Зокрема, числа Стірлінга першого роду підраховують перестановки відповідно до їх кількості циклів (вважаючи нерухомі точки як цикли довжиною один).
Означення
Вихідне визначення чисел Стірлінга першого роду було алгебричним вони є коефіцієнтами при розкладі [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 с.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V matematici osoblivo v kombinatorici chisla Sterlinga pershogo rodu vinikayut pri vivchenni perestanovok Zokrema chisla Stirlinga pershogo rodu pidrahovuyut perestanovki vidpovidno do yih kilkosti cikliv vvazhayuchi neruhomi tochki yak cikli dovzhinoyu odin OznachennyaVihidne viznachennya chisel Stirlinga pershogo rodu bulo algebrichnim voni ye koeficiyentami s n k displaystyle s n k pri rozkladi en x n x x 1 x n 1 displaystyle x n x x 1 x n 1 v stepeni zminnoyi x displaystyle x x n k 0 n s n k x k displaystyle x n sum k 0 n s n k x k Napriklad x 3 x x 1 x 2 1 x 3 3 x 2 2 x displaystyle x 3 x x 1 x 2 1x 3 3x 2 2x sho prizvodit do znachen s 3 3 1 s 3 2 3 s 3 1 2 displaystyle s 3 3 1 s 3 2 3 s 3 1 2 Zgodom bulo viyavleno sho absolyutni znachennya s n k displaystyle s n k cih chisel dorivnyuyut kilkosti perestanovok n displaystyle n elementnoyi mnozhini yaki rozkladayutsya v k displaystyle k neperehresnih cikliv Ci absolyutni znachennya yaki vidomi yak bezznakovi chisla Stirlinga pershogo rodu chasto poznachayutsya c n k displaystyle c n k abo n k displaystyle binom n k Napriklad nehaj n 3 displaystyle n 3 Taka mnozhina maye 3 6 displaystyle 3 6 perestanovok Najbilshu kilkist cikliv maye totozhna perestanovka i 1 2 3 displaystyle iota 1 2 3 tri cikli Dva cikli mayut tri perestanovki 1 23 2 13 3 12 displaystyle 1 23 2 13 3 12 i odin cikl mayut ta dvi perestanovki Takim chinom 3 3 1 displaystyle begin bmatrix 3 3 end bmatrix 1 3 2 3 displaystyle begin bmatrix 3 2 end bmatrix 3 i 3 1 2 displaystyle begin bmatrix 3 1 end bmatrix 2 Mozhna pobachiti sho voni uzgodzhuyutsya z poperednim rozrahunkom s n k displaystyle s n k pri n 3 displaystyle n 3 Bezznakovi chisla Stirlinga takozh mozhut buti viznacheni algebrichno yak koeficiyenti en x n x n x x 1 x n 1 k 0 n n k x k 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 Poznachennya sho vikoristovuyutsya na cij storinci dlya chisel Stirlinga ne ye universalnimi i mozhut superechiti poznachennyam v inshih dzherelah Poznachennya kvadratnih duzhok n k displaystyle begin bmatrix n k end bmatrix takozh ye zagalnim poznachennyam koeficiyentiv Gausa Podalshij prikladZobrazhennya znizu dovodit rivnist 4 2 11 displaystyle begin bmatrix 4 2 end bmatrix 11 simetrichna grupa na 4 ob yektah maye 3 perestanovki formi displaystyle centerdot centerdot maye 2 orbiti kozhna rozmirom 2 i 8 perestanovok formi displaystyle centerdot centerdot centerdot centerdot z 1 orbitoyu rozmiru 3 ta 1 orbitoyu rozmiru 1 ZnakiOznaki znakovih chisel Stirlinga pershogo rodu peredbachuvani i zalezhat vid parnosti n k displaystyle n k A same s n k 1 n k displaystyle s n k 1 n k Rekurentne spivvidnoshennyaBezznakovi chisla Stirlinga pershogo vidu mozhna obchisliti za vidnoshennyam rekurentnosti n 1 k n n k n k 1 displaystyle begin bmatrix n 1 k end bmatrix n begin bmatrix n k end bmatrix begin bmatrix n k 1 end bmatrix pri k gt 0 displaystyle k gt 0 z pochatkovimi umovami 0 0 0 displaystyle begin bmatrix 0 0 end bmatrix 0 i n 0 0 k 0 displaystyle begin bmatrix n 0 end bmatrix begin bmatrix 0 k end bmatrix 0 pri n gt 0 displaystyle n gt 0 Zvidsi odrazu viplivaye totozhnist dlya znakovih chisel Stirlinga pershogo rodu s n 1 k n s n k s n k 1 displaystyle s n 1 k n cdot s n k s n k 1 Algebrichne dovedennya Dovedemo dane vidnoshennya rekurentnosti vikoristovuyuchi oznachennya chisel Stirlinga z tochki zoru zrostayuchih faktorialiv Vikoristavshi oznachennya x n displaystyle x bar n mayemo x n 1 x x 1 x n 1 x n x n n x displaystyle x bar n 1 x x 1 x n 1 x n x bar n n x zvidsi x n 1 n x n x x n displaystyle x bar n 1 n cdot x bar n x cdot x bar n Za oznachennyam koeficiyent pri x k displaystyle x k v livij chastini ciyeyi rivnosti dorivnyuye n 1 k displaystyle begin bmatrix n 1 k end bmatrix V pravij chastini koeficiyent pri x k displaystyle x k v dodanku n x n displaystyle n cdot x bar n dorivnyuye n n k displaystyle n cdot begin bmatrix n k end bmatrix a v dodanku x x n displaystyle x cdot x bar n vidpovidno dorivnyuye n k 1 displaystyle begin bmatrix n k 1 end bmatrix Z rivnosti mnogochleniv viplivaye rivnist koeficiyentiv pri odnakovih stepenyah tomu vikonuyetsya rekurentne spivvidnoshennya Kombinatorne dovedennya dovedemo rekurentne spivvidnoshennya koristuyuchis oznachennyam chisel Stirlinga cherez kilkist cikliv tobto orbit Rozglyanemo utvorennya perestanovok n 1 displaystyle n 1 elementnoyi mnozhini z perestanovok n displaystyle n elementnoyi mnozhini priyednannyam odnogo novogo elementa Ce mozhna zrobiti dvoma sposobami Do kozhnoyi perestanovki n displaystyle n elementnoyi mnozhini podanoyi v ciklichnomu vidi priyednayemo odin cikl dovzhini odin z novim elementom Perestanovki z k displaystyle k ciklami n 1 displaystyle n 1 elementnoyi mnozhini utvoryuyutsya z perestanovok z k 1 displaystyle k 1 ciklami n displaystyle n elementnoyi mnozhini tomu yih ye n k 1 displaystyle begin bmatrix n k 1 end bmatrix Inshi perestanovki otrimayemo n displaystyle n z perestanovok elementnoyi mnozhini z k displaystyle k ciklami pripisuyuchi novij element do cikliv yaki ye pislya kozhnogo z nayavnih elementiv Cim sposobom z kozhnoyi pidstanovki n displaystyle n elementnoyi mnozhini otrimayemo n displaystyle n pidstanovok n 1 displaystyle n 1 elementnoyi mnozhini tomu mayemo n n k displaystyle n cdot begin bmatrix n k end bmatrix pidstanovok Zvidsi viplivaye rekurentne spivvidnoshennya Tablicya znachenNizhche navedeno trikutnij masiv bezznakovih znachen dlya chisel Stirlinga pershogo vidu podibnih za formoyu do trikutnika Paskalya Ci znachennya legko generuvati vikoristovuyuchi rekurentne spivvidnoshennya yake otrimane u poperednomu rozdili 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 1VlastivostiProsti totozhnosti Zauvazhte sho hocha 0 0 1 displaystyle begin bmatrix 0 0 end bmatrix 1 mi mayemo n 0 displaystyle begin bmatrix n 0 end bmatrix yaksho n gt 0 displaystyle n gt 0 i 0 k 0 displaystyle begin bmatrix 0 k end bmatrix 0 yaksho k gt 0 displaystyle k gt 0 abo bilsh zagalno n k 0 displaystyle begin bmatrix n k end bmatrix 0 yaksho k gt n displaystyle k gt n Takozh n 1 n 1 displaystyle begin bmatrix n 1 end bmatrix n 1 n n 1 displaystyle begin bmatrix n n end bmatrix 1 Podibni spivvidnoshennya za uchastyu chisel Stirlinga mayut misce i dlya mnogochleniv Bernulli Bagato spivvidnoshen dlya chisel Sterlinga vidtinyayut podibni vidnoshennya na binomialnih koeficiyentah Vivchennya cih tinovih vidnoshen nazivayetsya en i zavershuyetsya teoriyeyu en Uzagalnennya chisel Stirlinga oboh vidiv na dovilni skladni vhidni dani mozhut buti rozshireni cherez vidnoshennya cih trikutnikiv do polinomiv zgortki Sterlinga Div takozhChisla Stirlinga drugogo roduPrimitkiLiteraturaM J Yadrenko Diskretna matematika navchalnij posibnik K MP TViMS 2004 245 s