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


 

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

20628. Специфика живого 72 KB
  Предмет изучение задачи и методы биологииТри образа биологииАксиомы биологии 2. Предмет изучения задачи и методы биологии Биология совокупность или система наук о живых системах. Предмет изучения биологии все проявления жизни а именно: строение и функции живых существ и их природных сообществ; распространение происхождение и развитие новых существ и их сообществ; связи живых существ и их сообществ друг с другом и с неживой природой. Задачи биологии состоят в изучении всех биологических закономерностей и раскрытии сущности жизни.
20629. Термодинамика живых систем. Жизнь как информационный процесс 76.5 KB
  Термодинамика живых систем Состояние живых систем в любой момент времени динамическое состояние характерно тем что элементы системы постоянно разрушаются и строятся заново. Это означает что живые системы обязательно должны быть открытыми системами. Именно на этом неравновесии основана работоспособность живой системы направленная на поддержание высокой упорядоченности своей структуры а. Переход живо системы в такое состояние означает для нее смерть.
20630. Концепция эволюции в биологии 87 KB
  Концепция эволюции в биологии 1. Современная синтетическая теория эволюцииОсновные законы эволюцииОсновные факторы эволюцииФормы естественного отбора Контрольные вопросыЛитература Под эволюцией подразумевается процесс длительных постепенных медленных изменений которые в конечном итоге приводят к изменениям коренным качественным завершающимся образованием новых систем структур и видов. Представления об эволюции в естествознании имеют ключевое значение. [1] Парадигма современного естествознания это эволюционносинергетическая...
20631. Человек. колого-эволюционные возможности человека 110.5 KB
  Место человека в системе животного мира и антропогенез2. Основные этапы развития Человека Разумного3. Экологоэволюционные возможности человека5. Место человека в системе животного мира и антропогенез Вопрос о происхождении человека имеет не только научное значение: с позиций эволюционной биологии или чисто зоологической точки зрения это частный филогенетический вопрос.
20632. Биосфера и цивилизация 72.5 KB
  Живые организмы входящие в состав биоценоза неодинаковы с точки зрения специфики ассимиляции ими вещества и энергии из ОС. Совокупность множества параметров среды определяющих условия существования того или иного вида и его функциональных характеристик преобразование им вещества и энергии обмен информацией со средой и с себе подобными и др. Энергетика основа цивилизации и без производства достаточного количества энергии человечество не сможет существовать и развиваться. Сегодня главный производитель энергии теплоэлектростанции ТЭС...
20633. Основные концепции и перспективы биотехнологии 120.5 KB
  Расшифровка генома человека3. Пастер выяснивший роль микроорганизмов в брожении виноделие пивоварение и в возникновении болезней животных и человека. Исключительное значение для борьбы с заразными болезнями имел предложенный Пастером метод предохранительных прививок основанный на введении в организм животного или человека ослабленных культур болезнетворных микроорганизмов. Медицинская микробиология исследует микроорганизмы вызывающие заболевания человека и разрабатывает эффективные методы борьбы с ними.
20634. Принципы симметрии в научной картине мира 60.5 KB
  Принципы симметрии в научной картине мира 1. Понятие симметрии 2. Нарушение симметрии как источник самоорганизации Контрольные вопросыЛитература 1. Понятие симметрии Одним из важных открытий современного естествознания является тот факт что все многообразие окружающего нас физического мира связано с тем или иным нарушением определенных видов симметрий.
20635. Эволюционно-синергетическая парадигма. Открытость, нелинейность, диссипативность 64.5 KB
  4 Фазовое пространство и аттракторы системы Контрольные вопросыЛитература 1. В основе синергетики лежит среди прочих важное утверждение о том что материальные системы могут быть закрытыми и закрытыми равновесными и неравновесными устойчивыми и неустойчивыми линейными и нелинейными статическими и динамическими. Принципиальная же возможность процессов самоорганизации обусловлена тем что в целом все живые и неживые природные и общественные системы являются открытыми неравновесными нелинейными.Пригожин разрабатывая современную...
20636. Эволюционно-синергетическая парадигма 102 KB
  внутренняя структура или самоорганизация поддерживается за счет поглощения отрицательной энтропии или негэнтропии из окружающей среды. уводит ее от состояния равновесия максимума энтропии. В неравновесных системах помимо знания балансовых уравнений встает задача формализации и учета отношения порядка и беспорядка соответственно энтропии и негэнтропии. Рынок выступает здесь в качестве индикатора быстро обнаруживая неходовые товары производство которых нерентабельно и ведет к росту энтропии.