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.


 

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

75381. ХРОМАТИЧЕСКАЯ ДИСПЕРСИЯ В ОДНОМОДОВОМ ВОЛОКНЕ И УШИРЕНИЕ ПЕРЕДАВАЕМОГО ИМПУЛЬСА 113 KB
  В полосе прозрачности 850 нм более длинные волны распространяются с большей скоростью чем короткие например излучение на длине волны 865 нм распространяется в кварцевом стекле с большей скоростью чем излучение на длине волны 835 нм. Совсем наоборот происходит в полосе прозрачности 1550 нм: более короткие длины волн распространяются с большими скоростями чем более длинные излучение с длиной волны 1535 нм распространяется быстрее чем с длиной волны 1560 нм. Спектр оптического сигнала имеет конечную ширину ...
75382. МЕЖМОДОВАЯ ДИСПЕРСИЯ В МНОГОМОДОВОМ ВОЛОКНЕ 74 KB
  Импульсы излучения для мод более высоких порядков появляются на выходе из волокна позже Траектории лучей в градиентном волокне Многомодовое волокно со ступенчатым поперечным распределением показателя преломления Групповая скорость распространения света в волокне...
75383. МЕХАНИЗМЫ ВОЗНИКНОВЕНИЯ ПОТЕРЬ ИЗ-ЗА НЕСОВЕРШЕНСТВА ВОЛОКНА 50 KB
  Главная цель производителя оптоволокна получить более точную геометрию волокна. Три параметра как показала практика оказывают наибольшее влияние на характеристики сростка: концентричность сечений сердцевины и оболочки допуск на диаметр оболочки и собственный изгиб волокна. Улучшение этой характеристики при производстве волокна уменьшает шанс неточного расположения сердцевины что способствует получению сростков с меньшими потерями.
75385. Способы выражения информации о виде. Типы видовых основ и регулярные способы видообразования 25.5 KB
  Способы выражения информации о виде. Типы видовых основ и регулярные способы видообразования. Способы выражения информации о виде. с глаголами совершеного вида: нельзя сказать кончить прочитать редкий способ.
75386. Категория времени у причастий и деепричастий. Абсолютная и относительная временная ориентация. Условия конкуренции абсолютной и относительной ориентации в русском 20.46 KB
  Причастия сохраняют видовое значение глагола и при помощи специальных суффиксов выражают значение времени настоящего или прошедшего. Соответственно все причастия делятся на причастия настоящего и прошедшего времени. Причастия наст. Причастия прош.
75387. Типы употреблений форм времени. Настоящее актуальное и неактуальное. Переносные употребления форм времени 27.17 KB
  Настоящее актуальное и неактуальное. конкретизируется как настоящее момента речи . Выделяются две основные разновидности прямого употребления форм настоящего времени: настоящее актуальное конкретное настоящее время момента речи и настоящее неактуальное. Настоящее актуальное характеризуется признаком отнесенности действия к моменту речи: Кажется гдето звонят говорит АняЧех.
75388. Морфологическая категория лица 43.32 KB
  Значения и употребления форм 1го лица единственного и множественного числа С грамматической точки зрения наиболее устойчива и наименее многозначна форма 1го лица единственного числа как форма субъекта речи. Кроме того форма 1го лица единственного числа иногда служит для обозначения обобщенного субъекта и в этом случае индивидуальноличное значение ее ослабевает. Гораздо более сложны и разнообразны возможности непрямого переносного употребления 1го лица множественного числа. Так на формах глагола отражается экспрессивное...
75389. Морфологическая безличность 23.56 KB
  Морфологически безличный глагол имеет ограниченную парадигму: только форму 3 лица ед. и форму ср. Если у глагола есть форма мн. Речь идет только о наборе форм а не о семантике.