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.


 

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

42715. Электронные таблицы. Использование функций 140.5 KB
  Для облегчения поиска нужной функции все функции разделены на категории: математические статистические и т. После выбора функции в окне мастера имеется ссылка на справку по применению конкретной функции с примерами. При выполнении лабораторной работы читайте справочные сведения по каждой применяемой функции.
42716. Электронные таблицы. Использование функции Если 101.5 KB
  Использование функции ЕСЛИ И В приведенном ниже списке задана информация о сдаче сессии студентами. Учтите что в этом случае условие будет сложным с использованием функции И.
42717. Электронные таблицы. Построение диаграмм 237 KB
  Горизонтальная ось X ось категорий вертикальная ось Y ось значений. Горизонтальная ось X ось значений вертикальная ось Y ось категорий. они отображают зависимость данных ось Y от величины которая меняется с постоянным шагом ось Х.
42718. ОЦЕНКА ХАРАКТЕРИСТИК ПРОГРАММ НА ОСНОВЕ ЛЕКСИЧЕСКОГО АНАЛИЗА 199.5 KB
  Определить значения метрик Холстеда на основе которых дать оценку качества разработанного исходного текста программы.1 Реализация программы Текст программы для реализации возможного решения поставленной задачи разработанной с использованием языка программирования С приведен в таблице 1: Таблица 1 Текст программы для вычисления значения функции F Номер строки Строки программы 1 using System; 2 nmespce holsted 3 { 4 clss Progrm 5 { 6 sttic void Minstring[] rgs 7 { 8 double x y F; 9 chr check; 10 do 11 { 12 Console.2 Словарь программы В...
42719. Оценка характеристик программ на основе лексического анализа. Метрики 262.5 KB
  Наиболее ценным для практики является то что такая оценка может быть получена вручную на основе зрительного анализа текста программы либо автоматически с помощью специально разработанных программных анализаторов причем относительно несложных. Джилб предположил что логическая сложность должна являться значимым если не определяющим фактором для оценки стоимости программы на начальных этапах ее проектирования. Логическая сложность программы Джилб определяет как насыщенность программы условными операторами типа IFTHENELSE и...
42720. Оценка надежности программных средств 227.5 KB
  Она основана на предположении об экспоненциальной зависимости плотности вероятности интервалов времени между проявлением ошибок от интенсивности ошибок. Кроме того в модели полагается что интенсивность ошибок на каждом случайном интервале времени линейно зависит от количества оставшихся в программе ошибок. Если допустить что ошибка после ее каждого проявления устраняется и при этом в программный модуль не вносятся новые то интенсивность ошибок ti на интервале ti определяется следующим соотношением: 1 где N количество ошибок...
42721. Интерфейсы, делегаты, события 277.5 KB
  Таблица 1 Список используемых элементов управления Элемент управления Класс Описание textBox1 TextBox Окно ввода имени продавца textBox2 TextBox Окно ввода фамилии продавца textBox3 TextBox Окно ввода стажа продавца textBox4 TextBox Окно вывода списка продавцов textBox5 TextBox Окно ввода оклада продавца textBox6 TextBox Окно ввода имени менеджера textBox7 TextBox Окно ввода фамилии менеджера textBox8 TextBox Окно ввода стажа менеджера textBox9 TextBox Окно ввода оклада менеджера textBox10 TextBox Окно вывода зарплаты менеджера button1 Button...
42722. Поняття алгоритму. Блок схема запису алгоритмів 24 KB
  Мета: ознайомитись з поняттям алгоритм розглянути властивості алгоритму способи запису алгоритмів ознайомитись з правилами креслення схем алгоритму. Скласти схему алгоритму для обчислення виразу: Алгоритм последовательность действий приводящая к конкретному результату.
42723. Основы языка С# и знакомство с основными элементами управления C# 430 KB
  В C как и в C C нумерация элементов массива идет с нуля. Естественно что в нашем примере у массива 6 =23 элементов k[00] первый k[12] последний.rry Элемент Вид Описание Length Свойство Количество элементов массива по всем размерностям Rnk Свойство Количество размерностей массива BinrySerch Статический метод Двоичный поиск в отсортированном массиве Cler Статический метод Присваивание элементам массива значений по умолчанию Copy Статический метод Копирование заданного диапазона элементов одного массива в другой массив CopyTo...