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


 

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

2499. Основы русского языка 243 KB
  Разновидности языка. Культура речи. Коммуникативные качества культурной речи. Взаимосвязь речь – речевая культурная ситуация. Коммуникативно-конгитивный процесс. Речевые нарушения в устном и письменном высказывании.
2500. Определение понятия сердце в кардиоолгии 107.9 KB
  Краткие сведения об истории развития учения о сердце. Развитие крупных сосудов, выходящих из сердца и входящих в него. Понятие о проводящей системе сердца. Закономерности ветвления экстраорганных и интраорганных артерий. Источники развития непарной и полунепарной вен.
2501. Признаки объектов ОУ. Самоанализ урока 25.27 KB
  Цель: формирование представлений о признаках объекта на основе рассказа с пояснениями на примерах и выполнения практических заданий.
2502. Понятие права человека в мировой практике и в Республике Беларусь 308 KB
  Основополагающие принципы прав человека. Декларация независимости и Билль о правах (США). Международные пакты о правах человека 1966г. Всеобщая декларация прав человека. Основания ограничения прав и свобод человека и гражданина. Личные или гражданские права и свободы граждан Республики Беларусь.
2503. Техники в живописи - пуантилизм и техника мазками 24.59 KB
  Этот урок направлен на ознакомление учащихся с разнообразием техник в живописи. Формирование умений применять знания при решении практических творческих заданий. Ознакомить детей с различными изобразительными средствами для передачи изображений. Развитие восприятия цвета и колористического видения. Научить видеть особенности и отличительные признаки разных видов искусства.
2504. Организационные теории и организационные сруктуры 260.17 KB
  Классическая организационная теория. Теории организационного поведения. Теория институтов и институциональных изменений. Популяционно-экологическая (эволюционная) теория. Понятия, характеризующие строение организации. Линейные структуры управления.
2505. Статистическая проверка параметрических гипотез 97.31 KB
  Понятие о гипотезе. Виды гипотез. Ошибки первого и второго рода. Статистический критерий проверки нулевой гипотезы. Отыскание критической области. Сравнение двух дисперсий нормальных генеральных совокупностей. Проверка гипотез равенства математических ожиданий двух случайных величин.
2506. Немецкая классическая философия 209.01 KB
  Общие характеристики немецкой классической философии. Трансцендентализм философии И. Канта. Учение о трансцендентальном и эмпирическом субъекте познания. Анализ механизма процесса познания. Априоризм и агностицизм И. Канта. Морально-практическая философия И.Канта. Категорический императив. Соотношение морали и религии. Социально-философские идеи Канта.
2507. Понятие, сущность, функции и цели международного права 26.24 KB
  Международное право – это особая правовая система, регулирующая международные отношения его субъектов по средствам юридических норм, создаваемых путем фиксированного (договор) или молчаливо выраженного (обычай) соглашения между ними и обеспечиваемых принуждением, формы, характер и пределы которого определяются в межгосударственных соглашениях.