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.


 

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

46322. Разработка компоновки приспособления 117.5 KB
  Разработка компоновки приспособления Разработку общего вида приспособления начинают с нанесения на лист контуров заготовки. В зависимости от сложности приспособления вычерчивают несколько проекций заготовки. Разработку общего вида ведут методом последовательного нанесения отдельных элементов приспособления вокруг контуров заготовки. Более этого вычерчивают корпус приспособления который объединяет все перечисленные выше элементы.
46323. Составление расчетной схемы и исходного управления для расчета зажимного усилия Рз 202 KB
  Составление расчетной схемы и исходного управления для расчета зажимного усилия Рз Закрепление заготовки производится с помощью зажимных устройств различных конструкций. Принцип действия и конструкцию зажимного устройства конструктор выбирает исходя из конкретных условий выполнения операций: типа производства величин сил резания действующих на заготовку при выполнении операций конструктивных особенностей заготовки типа станка. Выбор коэффициента трения f заготовки с опорными и зажимными элементами. Выбор коэффициента трения заготовки с...
46324. Составление расчетной схемы и исходного уравнения для расчета исходного усилия Ри 359 KB
  Наряду с изменением величины исходного усилия силовой механизм может также изменять его направление, разлагать на составляющие и совместно с контактными элементами обеспечивать приложение зажимного усилия к заданной точке. Иногда силовые механизмы выполняют роль самотормозящего элемента, препятствуя раскреплению заготовки при внезапном выходе из строя привода.
46325. Расчет приводов зажимных устройств 73 KB
  Благодаря использованию более высокого давления жидкости по сравнению с пневмоприводом при тех же развиваемых усилиях имеет меньшие габариты и вес; масло обеспечивает смазку трущихся частей. 5 низкого давления и большой производительности и 4 высокого давления и малой производительности. После замыкания механизма упора зажимного элемента в деталях давления в системе увеличивается и напорный золотник 6 отключает насос низкого давления. В дальнейшем будет уже работать только насос высокого давления рис.
46326. Электромеханические приводы защитных устройств 58.5 KB
  Электромеханические приводы защитных устройств Электромеханические зажимные устройства ЭМЗУ состоят из электродвигателя передаточного механизма зажимных элементов. Электродвигатель работает кратковременно только при зажиме или отжиме поэтому в ЭМЗУ всегда имеется самотормозящая передача для фиксирования состояния системы после зажима и отключения двигателя. В квазистатических ЭМЗУ сила зажима создается только за счет электромагнитного момента двигателя и величина этой силы определяется настройкой динамометрирующих упругих элементов в...
46327. Выращивание зерновых и снижение затрат на их обработку 587.76 KB
  Однако в Россию завозится большое количество продуктов питания изза рубежа что способствует повышению продуктивной зависимости от стран запада и политическую зависимость страны. руб. руб. продукции руб.
46328. Проектирование приводной станции к полочному элеватору 1.74 MB
  Нахождение коэффициента запаса прочности. Нахождение коэффициента запаса прочности. Нахождение коэффициента запаса прочности Подбор подшипников по динамической грузоподъемности. Кинематический и энергетический расчет привода Мощность элеватора определяется по уравнению где Z производительность элеватора.
46329. Увеличение мощности пути железных дорог. Совершенствование машин с точки зрения ремонтопригодности 16.83 MB
  Увеличение мощности пути железных дорог требует усовершенствования технологии и организации ремонтнопутевых работ. Своевременный и качественный ремонт пути снижение затрат времени труда и эксплуатационных расходов повышение производительности труда достигает акиалной1 еханизацией путевых работ. Основным направлением в вопросе механизации путевых работ является создание высокопроизводительных машин обеспечивающих производство больших объемов работ в сравнительно небольшие окна и вынесение значительной части работ на путевые...
46330. Повышене результативности камерального контроля 172.9 KB
  Для достижения поставленной цели необходимо решить следующие задачи: изучить теоретические подходы к содержанию камеральной проверки определить её место и роль в системе государственного налогового контроля; исследовать нормативноправовой механизм камерального контроля в России; исследовать современное состояние контрольной деятельности на примере Межрайонной инспекции ФНС России; определить результативности камерального и выездного контроля сравнить их; разработать рекомендации по повышению результативности камерального контроля....