22901

Деякі теореми про перестановки

Доклад

Математика и математический анализ

Всі перестановки елементів a1a2an1an можна скласти таким чином. Будемо послідовно брати усі перестановки елементів a1a2an1 і дописувати до них елемент an на всі можливі місця. Транспозиція змінює парність перестановки.

Украинкский

2013-08-04

44.5 KB

0 чел.

Деякі теореми про перестановки.

Теорема 1. Число усіх перестановок, які можна скласти з n елементів, дорівнює n!

Доведення. Доведемо теорему індукцією по числу n елементів. Нехай n= 1. В системі лише один елемент a1, який утворює лише одну перестановку , 1=1!

Припустимо, що теорема виконується для всіх систем, які складаються з не більш, ніж n- 1 елементів, і нехай в системі n елементів a1,a2,…,an-1,an. За припущенням індукції в системі з n-1 елементів  можна скласти (n-1)! Перестановок. Всі перестановки елементів a1,a2,…,an-1,an  можна скласти таким чином. Будемо послідовно брати усі перестановки елементів a1,a2,…,an-1  і дописувати до них елемент an на всі можливі місця. Спочатку ставимо його перед першим елементом у фіксованій перестановці елементів a1,a2,…,an-1, потім перед другим і т.д., і нарешті за останнім. Число місць, на які можна поставити елемент an, дорівнює n. Таким чином, користуючись однією перестановкою чисел a1,a2,…,an-1 ,ми одержуємо n різних перестановок елементів        a1,a2,…,an-1,an .Перестановки не повторюються, тому їх число дорівнює  (n-1)!n=n!

Нехай в перестановці міняються місцями два елементи. Така операція називається транспозицією.

Теорема 2. Транспозиція змінює парність перестановки.

Доведення. Припустимо, в перестановці натуральних чисел міняються місцями елементи i  та j, причому для визначення будемо вважати що <j.

Спочатку розглянемо випадок, коли в початковій перестановці числа  і  стоять поруч  від перестановки  

α1, α1,.., αk,i,j,β1, β2,.., βk

ми переходимо до перестановки

α1, α1,.., αk,j,i,β1, β2,.., βk

Нехай  в початковій перестановці елементи утворюють t інверсій. В результаті транспозиції взаємне розміщення  α1, α1,.., αk,i1, β2,.., βs не змінюється. Також не змінюється і взаємне розміщення елементів  α1, α1,.., αk,j1, β2,.., βs  Таким чином число інверсій в перестановці може змінитися лише за рахунок чисел i та j. Оскільки ми припустили, що i < j, то в початковій перестановці вони інверсію не утворювали, а в заключній  утворюють. Тобто, в заключній перестановці  t+1 інверсій. Числа t і t+1 різної парності, а тому парність перестановки змінюється.

Нехай тепер в початковій перестановці між елементами  і  стоять  елементів  від перестановки

α1, α1,.., αk,i,γ1, ,γ2,…, ,γm,,j1, β2,.., βs

ми переходимо до перестановки

α1, α1,.., αk,j,γ1, ,γ2,…, ,γm,i1, β2,.., βs

Цей перехід можна зробити за допомогою сусідніх транспозицій елементів. Спочатку за допомогою сусідніх транспозицій переходимо до перестановки α1, α1,.., αk,i,j,γ1, γ2,…, ,γm1, β2,.., βs

.

Далі зробимо ще одну сусідню транспозицію і перейдемо до перестановки

α1, α1,.., αk,j,i,γ1, γ2,…, ,γm1, β2,.., βs

Нарешті, за допомогою m сусідніх транспозицій в зворотньому порядку приходимо до заключної перестановки α1, α1,.., αk,j,γ1, ,γ2,…, ,γm,i1, β2,.., βs.

Всього зроблено 2+1 сусідніх транспозицій. За доведеним вище, кожна сусідня транспозиція змінює парність перестановки. Таким чином, парність перестановки змінилась 2+1 разів. Це означає, що початкові і заключна перестановки різної парності.

Наслідок. При n≥2 число парних перестановок з n елементів дорівнює числу непарних і дорівнює .

Доведення. Припустимо, що n елементів утворюють p парних і q непарних перестановок. Оскільки n≥2, в кожній перестановці є елементи a1 і a2. В кожній парній перестановці міняємо місцями ці елементи. За теоремою 2 всі парні перестановки стають непарними, тобто одержуємо р непарних перестановок, а тому pq.. Аналогічно міняємо місцями елементи  і  в кожній непарній перестановці  одержуємо q парних перестановок. Тобто, qp.. З двох нерівностей pq, qp , одержуємо, що p=q. Але за теоремою 1, число всіх перестановок дорівнює n! Тому p+q=n! і p=q, звідки p=q=n!/2.


 

А также другие работы, которые могут Вас заинтересовать

37623. Составление плана осмотра объекта 61.83 KB
  Цель задачи: Определить сроки осмотра объекта по всем поданным объектам. Требуется: Вывести план выезда страхового агента на объект. Организационноэкономическая сущность: Данная задача предназначена для того чтобы направить страхового агента на объект в соответствии с желаемой датой указанной клиентом.
37624. Економіка інтелектуальної власності 172 KB
  Економіка інтелектуальної власності. Права на об’єкти інтелектуальної власності як товару. Особливості права інтелектуальної власності як товару. Інтелектуальна власність як нематеріальний актив.
37625. Учет рисков в страховании 63.17 KB
  Дано: Ведомость предварительной стоимости объекта страхования Справочник клиентов Заявка от клиента. Требуется: Определить предварительный расчет рисков по объекту страхования. Периодичность и область применения: Предварительный расчет рисков по объектам страхования на момент запроса составляется при поступлении заявки. Техноэкономическая эффективность: Автоматизированное составление вывести предварительный расчет рисков по объектам страхования на момент запроса существенно повысит эффективность работы организации.
37626. Расчет полной стоимости объекта страхования 61.45 KB
  Цель задачи: Осуществить полной расчет стоимости объекта страхования. Дано: Предварительный расчет рисков по объекту страхования Нормативы по скидочным предложениям Справочник объектов страхования Ведомость предварительной стоимости объекта страхования. Требуется: Произвести окончательный расчет рисков страхования.
37627. МЕТОДЫ СОРТИРОВКИ 22.16 KB
  ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №1 Тема: МЕТОДЫ СОРТИРОВКИ ОТЧЕТ ВЫПОЛНИЛ СТУДЕНТ ГР. Постановка задачи Выполнить сравнение трех видов сортировки: метод вставки метод стандартного обмена метод пузырька и метод простого выбора. Метод вставки
37628. Теоретично-експериментальні дослідження продуктивності стрілового крана на лабораторній моделі діючого комплексу 1.46 MB
  Стрілові крани – являють собою вантажопідйомні машини загальнопромислового і спеціального призначення. Вони можуть бути стаціонарними, пересувними, повно поворотними, неповно поворотними.
37629. Циклы в Pascal 25.7 KB
  Теоретическое введение Операторы цикла Операторы цикла используются для вычислений повторяющихся многократно. Блок ради выполнения которого и организуется цикл называется телом цикла. Проверка условия продолжения цикла и модификация параметра цикла. Один проход цикла называется итерацией.
37630. Табличный процессор MS EXCEL. Создание таблицы с расчетными формулами. Использование мастера функций 128 KB
  В левой части строки формул находится поле имен где содержится адрес выделенной ячейки или размер выделяемого диапазона. В средней части строки формул расположены три кнопки предназначенные для ввода и последующей обработки содержимого ячейки. Первая кнопка с крестиком позволяет отменить последнее действие по вводу или редактированию содержимого ячейки. Правая часть предназначена для отображения содержимого выделенной ячейки.
37631. Текстовый редактор MS WORD, дополнительные возможности 38.86 KB
  Цель работы – изучение редактора формул Microsoft Eqution; создание связанных и внедренных объектов в документе Word. Одним из таких средств в программе Microsoft Word является редактор формул Microsoft Eqution 3. Он позволяет создавать формульные объекты и вставлять их в текстовый документ. Простейшие формулы в Microsoft Word можно создавать используя различные атрибуты формата символов верхний индекс нижний индекс и др.