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.


 

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

9315. Договор финансовой аренды (лизинга) 30.5 KB
  Тема №15: Договор финансовой аренды (лизинга) -1- Понятие и содержание договора. По договору финансовой аренды (лизинга) арендодатель обязуется приобрести в собственность указанное арендатором имущество у определе...
9316. Договор аренды зданий и сооружений. Договор аренды предприятия 39 KB
  Тема №16: Договор аренды зданий и сооружений. Договор аренды предприятия. Понятие и исполнение договора аренды здания или сооружения. По договору аренды здания/сооружения арендодатель обязуется передать во временное ...
9317. Жилищное право 70.5 KB
  Тема №17: Жилищное право. ЖК РФ от 29 декабря 2004 года. Градостроительный кодекс 29.12.04 Закон РФ от 4 июля 1991 о приватизации Закон РСФСР от 18 октября 1991 о реабилитации жертв политических репрессий Закон РФ от 19.02.1993 года о вын...
9318. Права и обязанности сторон по договору найма 46 KB
  Тема №18: Права и обязанности сторон по договору найма. права и обязанности сторон по договору найма. права и обязанности сторон по договору коммерческого найма поднайм Наймодатель жилого помещения имеет...
9319. Изменение жилищных правоотношений 43 KB
  Тема №19: Изменение жилищных правоотношений. основания изменения договора социального найма основания расторжения договора социального найма расторжение договора коммерческого найма...
9320. Приватизация жилья 24 KB
  Тема №20: Приватизация жилья. Приватизация - бесплатная передача в собственность граждан РФ на добровольной основе занимаемых или жилых помещений в государственном...
9321. Безвозмездное пользование имуществом 42.5 KB
  Тема №21: Безвозмездное пользование имуществом. Понятие и элементы договора (договор ссуды) По договору безвозмездного пользования имущества одна сторона ссудодатель обязуется передать или передает вещь в безвозмезд...
9322. Общие положения о договоре подряда 60 KB
  Тема №22: Общие положения о договоре подряда. Общие положения По договору подряда одна сторона (подрядчик) обязуется выполнить по заданию другой стороны (заказчика) определенную работу и сдать результаты заказчику, а заказчик обязуется принять р...
9323. Договор бытового подряда. 46 KB
  Тема №23: Договор бытового подряда. Понятие ДБП. По ДБП подрядчик, осуществляющий соответствующую предпринимательскую деятельность, обязуется выполнить по заданию гражданина (заказчика) определенную работу, предназначенную удовлетворить бытовые ...