Числа Стирлинга первого рода — различия между версиями
Tindarid (обсуждение | вклад) (→Дополнительные тождества: Введен список) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 6: | Строка 6: | ||
Существует <tex> 11 </tex> разбиений перестановки из четырех элементов на два цикла: | Существует <tex> 11 </tex> разбиений перестановки из четырех элементов на два цикла: | ||
− | <tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> | + | <tex dpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> |
− | <tex dpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> | + | |
− | <tex dpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> | + | <tex dpi="130">(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> |
− | <tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> | + | |
− | <tex dpi="130">(1; 2)(3; 4)</tex> | + | <tex dpi="130">(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> |
− | <tex dpi="130">(1; 4)(2; 3)</tex> | + | |
− | <tex dpi="130">(1; 3)(2; 4)</tex | + | <tex dpi="130">(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> |
+ | |||
+ | <tex dpi="130">(1; 2)(3; 4)</tex> | ||
+ | |||
+ | <tex dpi="130">(1; 4)(2; 3)</tex> | ||
+ | |||
+ | <tex dpi="130">(1; 3)(2; 4)</tex> | ||
Заметим, что разбиения <tex dpi="130">(1)(2; 3; 4)</tex> и <tex dpi="130">(1)(2; 4; 3)</tex> считаются различными, так как цикл <tex dpi="130">(2; 3; 4)</tex> невозможно получить ни из подмножества <tex dpi="130">(1)</tex>, ни из подмножества <tex dpi="130">(2; 4; 3)</tex> с помощью циклического сдвига элементов. | Заметим, что разбиения <tex dpi="130">(1)(2; 3; 4)</tex> и <tex dpi="130">(1)(2; 4; 3)</tex> считаются различными, так как цикл <tex dpi="130">(2; 3; 4)</tex> невозможно получить ни из подмножества <tex dpi="130">(1)</tex>, ни из подмножества <tex dpi="130">(2; 4; 3)</tex> с помощью циклического сдвига элементов. |
Текущая версия на 19:23, 4 сентября 2022
Числа Стирлинга первого рода (англ. Stirling numbers of the first kind) — количество перестановок порядка с циклами. Числа Стирлинга I рода обозначаются как или .
Содержание
Пример
Существует
разбиений перестановки из четырех элементов на два цикла:
Заметим, что разбиения
и считаются различными, так как цикл невозможно получить ни из подмножества , ни из подмножества с помощью циклического сдвига элементов.Вычисление
Рекуррентное соотношение
Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление
элементов в виде циклов либо помещает последний элемент ( ый) в отдельный цикл способами, либо вставляет этот элемент в одно из циклических представлений первых элементов. В последнем случае существует различных способов подобной вставки. Например, при вставке элемента в цикл можно получить только разных цикла: . Таким образом, рекуррентность имеет вид:
Доказательство
Рассмотрим
:- По определению, данному выше:
Заметим, что коэффициенты
— этоАналогично можно сказать, что коэффициенты
— этоА коэффициенты
— это , так как степени при увеличатся на , а коэффициенты при этом не изменятся.Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед
, следовательно справедливо равенство:- или
Таблица значений
Найдём числовые значения
для малых и .n\k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
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 | |
9 | 0 | 40320 | 109584 | 118124 | 67284 | 22449 | 4536 | 546 | 36 | 1 |
Применение
Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении:
Следовательно, числа Стирлинга I рода позволяют перейти от базиса
к базису (одно из основных применений)Здесь [1]:
обозначим как возрастающие факториальные степени или символ ПохгаммераДля ясности рассмотрим пример, при котором
:- , здесь коэффициенты при — это , то есть:
Теорема: |
Числа Стирлинга I рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней . |
Доказательство: |
Индукция по :База: Для , — очевидно.Переход: Учитывая, что имеем:, Введём для первой суммы
При ,При .Следовательно, мы можем представить выражение в виде одной суммы: |
Дополнительные тождества
Как уже упоминалось ранее:
- , в общем случае , если
Также:
- Зафиксируем один элемент, и переставим оставшиеся всеми возможными способами. Повторений не будет, так как чтобы зафиксированный элемент совпал, нужно сдвинуть всю перестановку на , но тогда мы получим исходную перестановку.
- , очевидно
- Разбить элементов на множество можно только одним образом, а именно на множества состоящие из одного элемента и одно множество состоящее из двух. Так как нас интересуют только циклы, получаем выборку двух элементов из всех элементов(множество состоящее из двух элементов всегда является циклом).
- По аналогии с предыдущим тождеством получаем, что нас интересуют виды конкатенации множеств . Тогда искомая формула получается упрощением выражения , которая учитывает фиксацию элемента в трехэлементном множестве и повторения двухэлементных.
- Аналогично, учитываем только интересующие нас множества и получаем формулу .
Для целых, положительных
- Второе равенство доказывается путем постепенного спуска вниз:
- Чтобы доказать первое, будем использовать биекцию(из прошлого раздела) в факториальные степени, а также формулу .
- Разложим наше искомое выражение, используя формулу для факториальных степеней, и применив бином Ньютона для второго множителя. Тогда: . Немного преобразовав, получим:
- C другой стороны:
- Приравниваем эти два выражения и получаем искомую формулу.
- Доказательство аналогично предыдущему с учетом знакочередования в убывающих факториальных степенях.
- Постепенно раскладываем и получаем искомую формулу:
Связь между числами Стирлинга
Если числа Стирлинга I рода позволяют перейти от базиса
к базису ,то числа Стирлинга II рода играют обратную роль и позволяют перейти от базиса к базису
Следовательно, числа Стирлинга тесно связаны друг с другом, а их связь выражается формулой:
См. также
Примечания
Источники информации
- Graham, Knuth, and Patashnik: Concrete Mathematics Second Edition 1994, ISBN 0-201-55802-5 — 257-267 с.
- В. Липский: Комбинаторика для программистов 1988, ISBN 5-03-000979-5 — 49-50 с.