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


 

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

44356. Социальная мобильность, ее виды. Маргинализация индивидов и групп 17.79 KB
  Изучая неравенство членов общества, важно, чтобы они были в движущемся, функционирующем обществе. Поэтому учитывают социальную мобильность, т. е. переход индивида из одного социального статуса в другой (ребенок становится студентом, холостяк – семьянином).
44357. Управление качеством услуг гостиничного комплекса 1.8 MB
  Актуальность данной работы заключается в том, что поиск решения наиболее эффективного управления качеством услуг благоприятно повлияет на функционирование компании, сохранив и укрепив ее позицию, что в дальнейшем повлияет и на конкурентоспособность её в целом
44358. Магистерская диссертация: учебно-методическое пособие 213.5 KB
  Методические рекомендации по работе над Магистерской диссертацией разработаны с учетом стандарта организации: Система менеджмента качества. Изложены требования к содержанию и структуре магистерской диссертации регламент подготовки и защиты даны основные методические рекомендации по обработке экспериментальных данных и оформлению диссертации.4я73  Сибирский федеральный университет 2012 СОДЕРЖАНИЕ Введение...
44359. Кредитный и финансовые договоры 30.95 KB
  Большинство договорных обязательств, которые заключают участники гражданского оборота, представляют собой возмездные отношения. Как правило, они порождают денежные обязательства, в силу которых одна сторона обязуется передать вещь, оказать услугу, произвести работу
44360. Финансовое право. Н.М. Погребной 912.5 KB
  Данное учебное пособие написано с целью оказания учебно-методической помощи студентам и другим заинтересованным лицам при изучении ими основных положений по финансовому праву. Разработанный материал позволит студентам использовать его в ходе лекционных занятий, при подготовке к семинарским, практическим занятиям, при написании курсовых работ и подготовке к экзаменам.
44361. Выбор микропартикулята сывороточных белков для замены жиросодержащих компонентов плавленого сыра и диетической соли взамен поваренной 9.67 MB
  Сыродельные предприятия располагают значительными резервами подсырной сыворотки, которая практически не используется в производстве натуральных сыров. Переработка сыворотки осуществляется по двум основным направлениям: первое- использование сыворотки натуральной в сгущенном или сухом виде
44362. Проектирование полупроводникового преобразователя электрической энергии 2.73 MB
  Минимальный угол открывания слишком большой получение необходимого напряжения за счёт увеличения угла α при отсутствии трансформатора приводит к большим пульсациям тока нагрузки и теряет смысл применение многопульсных схем то питание схемы будем осуществлять через трансформатор. Расчет трансформатора Найдем требуемое значение фазного напряжения вторичной обмотки трансформатора по...
44363. ОСОБЕННОСТИ ХИМИЧЕСКИХ СВОЙСТВ АТОМАРНОГО КИСЛОРОДА И ВОДОРОДА 229.5 KB
  Разделить модификации водорода можно адсорбцией на активном угле при температуре жидкого азота. При очень низких температурах равновесие между ортоводородом и параводородом почти нацело сдвинуто в сторону последнего. При 80 К соотношение форм приблизительно...
44364. Технологія будівельного виробництва. Методичні вказівки 234 KB
  Склад робіт по винесенню проекту в натуру: складання схеми розбивки траси і рекогносцировці дільниці; винесення вісі колектора та двох крайніх дрен паралельних; одноразовий вимір та провіжування вісей колектора та двох крайніх дрен; провіжування вісей проміжних дрен з лінійним проміром по створах віх на крайніх дренах; висотна прив’язка нульового пікету колектора або одиничної дрени; Винос в натуру вісі колектора або одиночної дрени виконується за допомогою теодоліта і мірної стрічки від траси провідної мережі вищого порядку і...