22899

Поняття перестановки

Доклад

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

В перестановці елементи не повторюються. Поняття інверсії Будемо казати що два числа в перестановці натуральних чисел утворюють інверсію якщо та в перестановці стоїть раніше від . Наприклад в перестановці 4 2 1 3 інверсії утворюють пари чисел 42 41 43 21 Постановка називається парною якщо її елементи утворюють разом парне число інверсій і непарною якщо вони утворюють непарне число інверсій. Наприклад в перестановці 4 2 1 3 елементи утворюють 4 інверсії тобто перестановка парна.

Украинкский

2013-08-04

113 KB

3 чел.

Поняття перестановки.

Нехай дана  деяка скінчена система різних елементів  Перестановкою цієї системи називається будь-яке упорядковане розміщення цих елементів. Іншими словами, перестановкою є будь-яка послідовність, яка складається з цих елементів. В перестановці елементи не повторюються.

Наприклад, перестановками системи чисел 1, 2, 3, 4 є

1 2 3 4

4 1 3 2

3 2 4 1         

             і т. д.

Далі будемо розглядати переважно перестановки натуральних чисел.

Поняття інверсії

Будемо казати, що два числа  в перестановці натуральних чисел утворюють інверсію, якщо >  та в перестановці стоїть раніше від . Наприклад, в перестановці 4, 2, 1, 3 інверсії утворюють пари чисел (4,2), (4,1), (4,3), (2,1)

Постановка називається парною, якщо її елементи утворюють разом парне число інверсій, і непарною, якщо вони утворюють непарне число інверсій.

Наприклад, в перестановці 4, 2, 1, 3 елементи утворюють 4 інверсії, тобто перестановка парна. В перестановці 2, 1, 3, 4 інверсію утворює лише пара чисел (2,1), тому перестановка непарна. В перестановці 1, 2, 3, 4 немає жодної інверсії. Число інверсій дорівнює 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,i1, β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.

Поняття матриці.

Квадратною матрицею порядку n називається квадратна таблиця чисел, яка має n рядків і n стовпчиків.

.

Числа αij називаються елементами матриці. Положення кожного елемента в матриці визначається номерами рядка і стовпчика, в яких знаходиться цей елемент. Це положення часто позначається індексами. Наприклад,  елемент  знаходиться в -му рядку і  стовпчику матриці А.

Визначники другого  і третього порядків формально записуються у вигляді квадратних таблиць чисел.

,   .

Числа в цих таблицях називаються елементами визначника. Кожному такому визначнику відповідає квадратна матриця відповідно порядків 2 і 3.

                       

При цьому можна сказати, що визначник Δ2 є визначником матриці A2 , а визначник Δ3  - визначником матриці A3.

Положення кожного елемента визначника, як  елемента матриці, визначається номерами рядка і стовпчика, як часто позначаються парою індексів.

Поняття визначника n- го порядку.

Спочатку з’ясуємо деякі закономірності в будові визначників другого і третього порядків. Беремо визначник 2 порядку.

Визначник є алгебраїчною сумою 2=2! Добутків пар елементів. В кожному добутку по одному і лише по одному елементу з кожного рядка і кожного стовпчика визначника. При цьому присутні всі можливі добутки, побудовані за таким правилом. Половина добутків в сумі береться зі знаком „+”, а половина – зі знаком  „-”.  Співмножники в кожному добутку можна упорядкувати за першим індексом. При зростаючому першому індексі другі індекси утворюють деяку перестановку чисел 1 і 2. В першому добутку при упорядкуванні за першим індексом другі індекси утворюють перестановку 1, 2. В цій перестановці 0 інверсій, тобто вона парна. Знак перед добутком „+”. В другому добутку при упорядкування за першим індексом другі індекси утворюють перестановку 2,1. В перестановці 1 інверсія, вона не парна, знак перед добутком „-”.

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

.

Визначник є алгебраїчною сумою 6=3!  добутків трійок елементів. В кожному добутку по одному і лише по одному елементу з кожного рядка і кожного стовпчика визначника. Половина добутків в сумі береться зі знаком „+”, а половина – зі знаком  „-”.  Співмножники в кожному добутку можна упорядкувати за першим індексом. При зростаючому першому індексі другі індекси утворюють деяку перестановку чисел 1, 2, 3. Візьмемо, наприклад, добуток a13 a21a32.. При упорядкуванні співмножників за першим індексом другі індекси утворюють перестановку 3, 1, 2. В цій перестановці дві інверсії, перестановка парна, знак перед добутком „+”. Візьмемо добуток  a11a23a32. Після упорядкування за співмножників за першим індексом другі індекси утворюють перестановку 1, 3, 2. В перестановці 1 інверсія, вона непарна, знак при добутку „-”.

Таким чином закономірності, які визначаються для визначників другого порядку, вірні і для визначників третього порядку.

Нехай задана деяка квадратна матриця порядку n.

Означення. Визначником n- го порядку  матриці А називається алгебраїчна сума всіх можливих добутків її елементів, побудованих за правилом: з кожного рядка і кожного стовпчика в добуток береться по одному і лише по одному елементу. Якщо після упорядкування елементів в добутку за першим індексом другі індекси утворюють парну перестановку, то перед добутком ставиться знак „+”, якщо непарну, то знак „-”.

Визначник матриці А позначається так:

Визначник також називається детермінантом. Для визначника матриці А також існують позначення:

Зрозуміло, що визначник n- го порядку є сумою n! добутків. Дійсно, кожен добуток можна упорядкувати за першим індексом, тобто записати вигляді

Де перестановка других індексів α1, α2,…, αn є деякою перестановкою чисел 1, 2, ..., n. За теоремою 1 про перестановки число всіх можливих таких перестановок n!, число всіх добутків дорівнює числу перестановок, тобто n!

Приклад.

Серед добутків, що складають визначник Δ, є добуток чисел -5, 5, -3, 6, які стоять відповідно у 1-му рядку і 3-му стовпчику, у 2 рядку і 1-му стовпчику, у 3-му рядку і другому стовпчику, у 4-му рядку і 4-му стовпчику. Перший індекс елемента визначає номер рядка, а другий – номер стовпчика. Таким чином, в даному добутку після упорядкування співмножників за першим індексом другі індекси утворюють перестановку 3, 1, 2, 4. В цій перестановці 2 інверсії, перестановка парна. Тому добуток (-5) 5 (-3)6 у визначнику  береться зі знаком „+”.

PAGE  4


 

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

68321. Механизм функционирования финансового менеджмента и его место в системе управления организацией 160 KB
  Рассмотреть цели, задачи и принципы финансового менеджмента; определить базовые концепции и функции финансового менеджмента; установить сущность и структуру финансового менеджмента; выявить место финансового менеджмента в системе управления организацией и механизмы его функционирования.
68322. Функції мікрофлори ШКТ, можливі порушення, профілактика 128.5 KB
  Життєдіяльність людини не можлива без нормального функціонування єдиного екологічного комплексу макро- і мікроорганізму. За останні 20-30 років зросла кількість різних патологічних станів, в основі яких є порушення нормального мікробіоценозу організму людини – дисбактеріоз.
68324. Транспозон. Типи транспозонів та механізми їх пересування 36.5 KB
  Мобільні генетичні елементи за типом транспозиції можна поділити на два класи: ДНК-транспозони які застосовують метод вирізати й вставити та ретротранспозони пересування яких має в своєму алгоритмі синтез РНК з ДНК та подальшим зворотнім синтезом ДНК з молекули РНК тобто метод копіювати й вставити.
68325. УЧЕБНЫЙ ПЛАН 32 KB
  В ответ нам покажут один максимум три листика с аккуратным указанием количества часов по каждому предмету в каждом классе. То есть практически учебный план сетка часов. Учебный план должен состоять из двух частей: объяснительная записка и сетка часов.
68326. УЧЕБНАЯ ПРОГРАММА 74.5 KB
  Нормативный текст определяющий цели ценности образования учебный план учебные программы педагогические технологии и методики их практической реализации и определения результата. Организационно-управленческое знание позволяющее реализовать принцип личностной ориентации...
68327. Учебник. Учебный материал 66 KB
  Как известно содержание единицы учебника параграфы главы характеризуется следующими параметрами: структурная сложность число разнородных единиц элементов их иерархия связи и отношения; содержательная сложность категория цели; информативность степень изменения тезауруса учебника...
68328. Формы, уровни, содержание и участники процесса правового обучения 236 KB
  Формы и уровни содержание гражданско-правового юридического образования право как обучение. Формы и уровни содержание гражданско-правового образования право как предмет обучения. Уровни образования. Законодатель допускает возможность получения образования в следующих формах каждая из которых есть особый способ...
68329. Управление и нормативно-правовое регулирование в области правого обучения 166 KB
  Нормативно-правовые акты регламентирующие процесс обучения. Муниципальная система образования это территориально обособленная и относительно самостоятельная часть системы образования республики взаимосвязанная с другими аналогичными частями.