Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2022-05-08 | 86 |
5.00
из
|
Заказать работу |
|
|
Декремент. Числа Стирлинга первого рода.
Мы уже знаем, что количество всех перестановок порядка n равно , а количество тех из них, которые не сохраняют на месте ни одно число, называется число беспорядков, или субфакториал, и равно .
Иногда удобно рассматривать не перестановку, а именно подстановку, то есть биекцию n-элементного множества на себя.
здесь .
Если рассмотреть композицию , то получится другая подстановка:
1 перешло в 2, затем 2 в 3, в итоге 1 в 3.
Куб этой подстановки приведёт к тождественной.
Бывает так, что при любой степени подстановки некоторое подмножество остаётся замкнутым относительно всех этих операций, то есть отображается только на само себя. В данном примере это два подмножества {1,2,3} и {4}. Они образуют независимые циклы.
= (231)(4) краткая запись.
Другой пример: = (21)(43)
Изучим, как меняется количество циклов при транспозиции элементов , взятых из одного цикла или разных циклов.
1) Поменяем местами пару элементов, находящихся в одном и том же цикле, например 2 и 3. Стало = (31)(2)(4).
один цикл распался на два, стало 3 цикла.
2) Поменяем местами пару элементов, находящихся в разных циклах, например 2 и 4 в
= (4231) стал один цикл, 2 цикла объединились.
Декремент подстановки.
Пусть подстановка n-й степени разложена в произведение циклических подстановок. Пусть — число циклических подстановок-сомножителей (в том числе циклов длины 1). Тогда декрементом называется разность .
В примере = (231)(4), .
Сама перестановка чётная (инверсии только 2,1 и 3,1) и декремент тоже чётный.
Теорема. Декремент четен для четной подстановки и нечетен для нечетной подстановки.
Доказательство. Если изначально рассмотреть тождественную подстановку, то она содержит n циклов, каждый состоит из одного элемента. Она чётна, так как 0 инверсий. При этом = тоже чётно.
|
Мы можем перейти к искомой подстановке с помощью серии транспозиций. Первая из них (после тождественной) меняет 2 элемента, становится 1 цикл из двух элементов и одноэлементных цикла, чётность подстановки сменилась, и чётность декремента тоже, так как . Далее каждый раз при транспозиции меняется чётность, а один цикл либо появляется, либо исчезает (в зависимости от того, меняем мы элементы из одного цикла или из разных), то есть чётность декремента тоже меняется при каждой транспозиции синхронно с чётностью подстановки.
Для больших n легче разложить в произведение циклов и найти декремент, чем все инверсии (n действий по сравнению (n^2 – n)/2).
Пример.
равен , так как здесь 3 цикла. Подстановка нечетна (все инверсии искать не требуется, чтобы утверждать это).
Числа Стирлинга первого рода (без знака) — количество перестановок порядка n с k циклами. Обозначается .
n=2
2 цикла - одна перестановка: (12)
1 цикл - одна перестановка: (21)
n=3
3 цикла - одна перестановка: (123)
2 цикла - 3 перестановки: (213) (321) (132)
1 цикл - 2 перестановки: (231) (312)
По крайней мере, начало таблицы чисел Стирлинга 1 рода мы можем составить:
Точно известно, что перестановок порядка n с n циклами всего одна, и она тождественная.
Отличие от чисел Стирлинга 2 рода: там рассматриваются только подмножества, а здесь, разбив n-элементное множество на подмножества, внутри каждого ещё можно по-разному переставить элементы, то есть для каждого подмножества ещё может быть несколько подстановок, поэтому числа Стирлинга 1 рода больше или равны, чем соответствующие числа Стирлинга 2 рода..
.
Сначала изучим, сколько может быть перестановок с одним циклом.
Их количество . Докажем этот факт.
Пусть 1 переходит в какое-то число , должно быть в одно из оставшихся, но не в 1 (иначе уже был бы отдельный цикл только из одного элемента, а значит, количество циклов было бы ).
|
отображается в , где любое из оставшихся кроме 1 и .
Если было бы и , то был бы отдельный 2-элементный цикл, а значит снова единый цикл из n элементов не получился бы.
вообще исключено, так как , а в подстановке во 2 строке не могут быть два одинаковых числа, ведь подстановка это биекция.
Таким образом, вариантов уже . Далее должно отобразиться в одно из оставшихся элементов, и.т.д до последнего, где останется только 1 вариант. на последнем шаге, иначе цикл завершится раньше, и будет не 1 а больше циклов.
((21)(43) является беспорядком, но не одним циклом).
Число подстановок с одним циклом:
=
Мы уже посчитали следующие числа Стирлинга 1 рода:
ЛЕКЦИЯ 7. 4.3.2021
Теперь нам снова нужно вывести какую-то рекуррентную формулу, с помощью которой числа Стирлинга можно найти с помощью предыдущих и заполнить всю таблицу до любых требуемых .
Верна следующая рекуррентная формула:
Доказательство. Рассмотрим все случаи, как в перестановке из чисел могут образоваться циклов.
1) Если в перестановке из чисел было циклов, а новое число на последнем месте, то оно образует -й цикл.
Число таких вариантов .
2) Если в перестановке из чисел было циклов, число на последнем месте образовало бы -й цикл, если его затем поменять с любым меньшим числом, которых имеется , то два цикла объединятся и их количество станет . Число таких вариантов .
3) Если в исходной подстановке порядка было и менее, либо и более циклов. В этом случае тоже можно привести к , но уже с помощью серии из нескольких транспозиций, где число будет переставлено несколько раз. Однако эти случаи учитывать не надо, так как они уже учтены: ведь если попадает на какое-то место , то можно было заранее осуществить некоторые транспозиции в исходной перестановке, чтобы потом поменять с чем-то только 1 раз. А такие перестановки все уже учтены.
Итак, .
В отличие от чисел Стирлинга 2 рода, где было
здесь надо элемент слева и сверху по диагонали, прибавить к тому, который ровно над искомой клеткой, но умножать его не на номер столбца, а на номер строки (той, которая выше).
,
,
Начало таблицы для чисел Стирлинга 2 и 1 рода:
|
Ниже 11 будет число .
С помощью рекурсии можно найти и все остальные числа.
В каждой строке получается число всех перестановок порядка , то есть , и эти числа больше или равны, чем числа Белла (равны лишь при и ). Там была последовательность: 1, 2, 5, 15, 52,...
а здесь 1, 2, 6, 24, 120,...
|
|
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!