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.


 

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

36475. Неолитическая цивилизация 51.5 KB
  лесов быстро исчерпались Саванны – нет земледелия переселение в субтропики Неолитическая катастрофа выжило 1000 чел Начало новой ц.
36476. Древняя Персия 27 KB
  За помощь в осуществлении контроля над обществом им предоставлялась наибольшая политическая самостоятельность Частный интерес работает на общественный Внешняя политика Восточное побережье Эгейского моря Греция – колонии господство над торговлей в средиземном море Внешняя политика обусловлена экономической структурой: цель – экономически важные регионы.
36477. Древние Шумеры 30.5 KB
  долина рек Тигр и Ефрат Неблагоприятные условия сухой климат мало полезных ископаемых Тростник и рыба – самые доступные ресурсы Население сосредоточено в предморье и не углублялось во влажные равнины Увеличение численности населения перенаселение Технологии Сельскохозяйственные культуры ячмень эммера Одомашнен ряд животных быки овцы козы свиньи и ослы Примитивные технологии обработки меди Колесо Первые постройки из сырого глиняного кирпича Шумеры пытаются вести с х на новых землях строят системы очищения почвы....
36478. Понятия «цивилизация». Подходы к толкованию термина. Цивилизационная теория 93.5 KB
  Понятия цивилизация впервые употребил Виктор Мирабо в 1757 году в значении общего уровня культурного развития. Среди деятелей просвещения цивилизация ассоциировалась с концепцией прогресса стала идеалом интеллектуального и социального развития человечества. Отсюда ясно что цивилизация носила отрицательный оттенок.
36479. Структура цивилизация, ее основные элементы 73 KB
  технологический способ производства: орудия труда источники энергии предметы труда природные ресурсы технологии организация производства в плане технологий экономический способ производства структура воспроизводства обмен распределение экономическое управление социальнополитические отношения: социальные отношения национальные отношения политические отношения государственные отношения правовые духовный мир: наука культура образование мораль идеология или религия Все элементы цивилизационной...
36480. Динамика развития цивилизации, этапы ее развития на историческом примере 46.5 KB
  В истории человечества выделяют следующие глобальные цивилизации: неолитическую раннеклассовую античную средневековую индустриальную и наконец постиндустриальную цивилизации. Условия формирования античной цивилизации. Безусловно их наследие оказало определенное влияние на становление античной цивилизации тем не менее античный период в истории человечества дал рождение совершенно новым экономическим политическим и духовным институтам.
36481. Переходный период (смена цивилизаций): основные этапы и итоги 35 KB
  Механизм смены цивилизации Основные причины: внутренние противоречия в которых центральное место занимают потребности человека. Для производства материальных и духовных благ цивилизации приходится привлекать новые ресурсы средства труда источники энергии реализовывать новые экономические и политические схемы подавлять социальные конфликты и предлагать новый духовный продукт. Попытки удовлетворения потребностей нарушают сложившийся в цивилизации баланс и она не может удовлетворить потребности всех. Духовный мир чутко реагирует на эти...
36482. Переходный этап в развитии цивилизации на историческом примере перехода от раннеклассовой к античной 27.5 KB
  Переход между цивилизациями происходит в четыре этапа: латентный этап обвального хаоса патовая ситуация завершающий этап. На первом этапе происходит падение эффективности старого общества: возникают социальные противоречия разногласия между управленцами и исполнителями экономической функции и непрерывные войны которые с одной стороны истощали материальные ресурсы а с другой обогащали правящую элиту. Происходит возращение к родоплеменному типу отношений формирование общинного строя предполагающего управление общества вождем советом...
36483. Основные особенности и достижения неолитической цивилизации 32 KB
  Начало неолитической цивилизации связывают с неолитической революцией. Достижения неолитической цивилизации: Возникла первая форма собственности общинная собственность на землю; Появляется объекты собственности сельскохозяйственные земли пастбища охотничьи и рыболовные угодья; Возникает частная собственность при необходимости – защита частной собственности; Формирование первых политических институтов крупные межобщинные объединения; Духовный мир выходит на новый уровень возрастает уровень познания окружающего мира;...