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.


 

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

10022. Инновационные технологии в проектировании нового туристического продукта 509.4 KB
  Инновационные технологии в проектировании нового туристического продукта Введение Актуальность дипломного исследования. Прошедший ХХ век наряду со многими феноменальными событиями и явлениями в жизни мирового сообщества продемонстрировал чуть ли не взрывной ха...
10023. Моделирование кривых титрования с помощью MathCad 49.5 KB
  Моделирование кривых титрования с помощью MathCad. Рассматривается пример построения кривой титрования в Mathcad. Постановка задачи и порядок выполнения работы описывается в соответствующей обучающей программе. Студенты должны запустить Mathcad и обучающую программу Титрова...
10024. Программирование в MathCAD 167 KB
  Программирование в MathCAD Панель инструментов Программирование Язык программирования Mathcad Для вставки программного кода в документы в Mathcad имеется специальная панель инструментов Программирование. Большинство кнопок этой панели выполнено в виде текстового пре
10025. Принципы усиления сигналов и построения усилителей 991.5 KB
  Тема № 1. Принципы усиления сигналов и построения усилителей. Занятие № 1. Принципы электронного усиления сигналов. Учебные методические и воспитательные цели: Изучить принципы усиления и построения усилителей их параметры. Сконцентри...
10026. Каскады предварительного усиления 902 KB
  Тема № 2. Каскады предварительного усиления Занятие № 1. Широкополосные усилители Учебные методические и воспитательные цели: 1. Изучить принципы построения и функционирования каскадов предварительного усиления и широкополосных усилителе...
10027. Оконечные усилительные каскады 1.1 MB
  Тема № 3. Оконечные усилительные каскады Занятие № 1. Принципы построения и функционирования каскадов оконечного усиления Учебные методические и воспитательные цели: 1. Изучить принципы построения оконечных усилительных каскадов. 2. Со...
10028. Преобразователи частоты. Общие принципы преобразования частоты 950.5 KB
  Тема 4. Преобразователи частоты Занятие 1. Общие принципы преобразования частоты Учебные методические и воспитательные цели: 1. Изучить сущность принципов преобразования частоты. 2. Изучить схемы и принципы работы диодных преобразователей ...
10029. Функциональные устройства на операционных усилителях 810.5 KB
  Тема 5. Функциональные устройства на операционных усилителях Занятие 1. Аналоговые электронные устройства на операционных усилителях Учебные методические и воспитательные цели: 1. Изучить основные свойства операционных усилителей ОУ...
10030. Роль и место дисциплины в подготовке офицера связиста 236.5 KB
  Вводная лекция Учебные методически развивающие и воспитательные цели: 1. Уяснить роль и место дисциплины в подготовке офицера связиста изучить основные определения классификацию технические показатели и характеристики аналоговых электронны