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.


 

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

22352. Представление аналитических функций рядами 464 KB
  Ряды Тейлора. при каких условиях функция представима своим рядом Тейлора с центром в точке : 4 даёт Теорема 1 Коши. Функция представима своим рядом Тейлора 4 в любом открытом круге с центром в точке в котором она аналитична.
22353. Ряды Лорана 269.5 KB
  Поэтому обе формулы можно объединить в одну: 7 Полученное разложение 6 функции fz по положительным и отрицательным степеням za с коэффициентами определяемыми по формулам 7 называется лорановским разложением функции fz с центром в точке a; ряд 2 называется правильной а ряд 4 – главной частью этого разложения. и в нашем рассуждении могут быть взяты сколь угодно близкими к r и R а q может сколь угодно мало отличаться от 1 то разложение 6 можно считать справедливым для...
22354. Примеры особых точек 2.06 MB
  Функции имеют в начале координат устранимую особую точку. Функции имеют начале координат существенную особую точку. Проверим справедливость теоремы Сохоцкого для функции . Целые функции.
22355. Бесконечно удаленная точка 682.5 KB
  Пусть функция аналитична в некоторой окрестности бесконечно удаленной точки кроме самой точки . В этом случае функция очевидно ограничена и в некоторой окрестности точки . Пусть функция аналитична в полной поскости. Но тогда функция ограничена во всей плоскости: для всех имеем .
22356. Приложение теории вычетов 797 KB
  Напомним что мероморфной называется функция fz все конечные особые точки которой являются полюсами. в любой ограниченной области такая функция может иметь лишь конечное число полюсов то все ее полюсы можно пронумеровать например в порядке не убывания модулей: Будем обозначать главную часть fz в точке т. Если мероморфная функция fz имеет лишь конечное число полюсов и кроме того является либо правильной регулярной ее точкой либо полюсом то эта функция представляется в виде суммы своих главных частей 3 и...
22357. Обращение степенных рядов 217.5 KB
  Выберем число столь малым чтобы в круге функция обращалась в нуль только в точке . Каждое значение из круга функция принимает в круге только один раз. В самом деле на окружности выполняется неравенство и по теореме Руше функция имеет в круге столько же нулей сколько и функция т. Итак пусть тот круг в котором функция принимает каждое значение ровно один раз а область плоскости ограниченная кривой кривая является простой кривой т.
22358. Аналитическое продолжение 680.5 KB
  Представляет большой интерес вопрос нельзя ли расширить область определения этой функции сохранив регулярность. Функцию регулярную в области содержащей и совпадающую с регулярной в области называют аналитическим продолжением функции на область . Если аналитическое продолжение регулярной функции в данную более широкую область определения возможно то оно возможно лишь единственным образом. В самом деле пусть существуют два аналитических продолжения и функции регулярной в области в одну и туже область .
22359. Римановы поверхности 55 KB
  Пусть дана многозначная аналитическая функция fz определенная в области D комплексной плоскости. Условимся рассматривать области Dk из которых в процессе аналитического продолжения строится область D как отдельные листы изготовленные в таком количестве экземпляров сколько значений имеет функция в данной области D. Пусть области D0 и D1 имеют общие части причем в одних из этих частей значения f0z и f1z совпадают а в других различны. Поверхность образованную из отдельных областей определения ветвей многозначной аналитической...
22360. Конформные отображения. Понятие конформного отображения 1.86 MB
  Предположим что задано непрерывное и взаимно однозначное отображение области D на некоторую область . Геометрически эта замена равносильна замене отображения отображением 3 которое называется главной линейной частью отображения 1. Отображение 3 можно переписать в виде 4 где: 5 не зависят от x и y. Отображение 4 представляет собой так называемое линейное аффинное преобразование плоскости .