Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Перестановки и подстановки.
Рассмотрим множество М целых чисел: 1, 2, …, n. Элементы множества М можно расположить разными способами.
В качестве можно выбрать любое из чисел 1, 2, …, n. Это дает n различных возможностей. Если уже выбрано, то в качестве можно выбрать лишь одно из оставшихся (n -1) чисел, т.е. различных способов выбрать числа (символы) и равно произведению n∙ (n -1) и т.д. Число перестановок из n символов равно произведению: Если в некоторой перестановке поменяем местами какие-либо два символа, не обязательно стоящие рядом, а все остальные оставим на месте, то получим новую перестановку. Такое преобразование перестановки называется транспозицией.
► Доказательство проведем методом математической индукции. При n =2 утверждение справедливо: 1) так как: 2! = 1·2 = 2, то всего перестановок 2; 2) пусть 1-я перестановка: 1, 2 → тогда 2-я: 2, 1; 3) пусть 1-я перестановка: 2, 1 → тогда 2-я: 1, 2. Пусть для (n -1) символов теорема выполняется. Рассмотрим все перестановки из n элементов, у которых на первом месте стоит символ (не перемещается!). Таких перестановок (n -1)! и их можно (в соответствии с предположением) упорядочить так, как требует теорема. Пусть последняя из таких перестановок имеет вид: , , …, , (2) В перестановке (2), содержащей n символов, совершим транспозицию символа с любым другим (например, с символом ) и вновь упорядочим все перестановки из (n -1) символов при фиксированном на первом месте и т.д. Так поступим n раз. Это обеспечит перебор всех n! перестановок для n символов. ◄ Следствие: от любой перестановки из n символов можно перейти к любой другой перестановке из тех же символов при помощи нескольких транспозицией. Если в перестановке символ стоит раньше, чем символ , но > , то говорят, что символы и составляют инверсию (нарушение порядка), иначе указанные символы составляют порядок. Перестановка называется чётной, если ее символы составляют чётное число инверсий, и нечётной – в противном случае.
► Пусть транспонируются символы: ☺ и ☻. Отметим символом ♦ те символы перестановки, которые транспозицией не затрагиваются. Рассмотрим два возможных случая: 1) перестановки имеет вид: ♦ ♦ ♦ ♦ ☺ ☻ ♦ ♦ ♦ ♦ ♦ и символы ☺ и ☻ не составляют инверсию; к выделенным символам применим одну транспозицию: ♦ ♦ ♦ ♦ ☻ ☺ ♦ ♦ ♦ ♦ ♦ → теперь символы ☻ и ☺ составляют инверсию. 2) пусть перестановка записана в виде:
В исходном положении символы ☺ и ☻ разделяют некоторые k символов. Если бы мы решили сразу поменять местами выделенные элементы, то не смогли бы оценить изменение их взаимоотношений с разделяющими их элементами! Поэтому берём элемент ☻, и, обмениваясь местами только с соседним левым элементом, движемся влево... На последнем шаге меняются местами выделенные элементы. Теперь имеем рядом элементы: ☻ и ☺. На такое преобразование потребовалось (k+1) транспозиций. Для того, чтобы элемент ☺ переместился на исходное место элемента ☻, ему потребуется k транспозиций. Итак, мы обеспечили выделенным элементам транспозицию, применив 2k+1 легко учитываемых транспозиций. Так как число 2k+1 есть нечётное число, то это значит: если символы ☺ и ☻ не составляли инверсию, теперь составляют. И наоборот! ◄
► Пусть исходная запись перестановки ☺: 1, 2, …, n; нарушений порядка нет. Запишем теперь перестановку в виде ☻: n, (n-1), …, 2, 1; теперь нарушений порядка наибольшее число. От перестановки ☺ к перестановке ☻ можно перейти, используя минимальное число транспозицией: N = . Этот результат легко прочитывается из схемы, использованной при доказательстве теоремы 3.2. ◄ Анализируя рассмотренные свойства перестановок, замечаем: для формирования индексов одного из множителей общего члена определителя: · ·…· требуется совместное использование двух перестановок: , ,..., и , ,..., . При этом: указывает номер строки, а номер столбца, выбираемых для выделенного множителя члена определителя. Заметим также, что для определителя удобно последовательность , ,..., заменить последовательностью: 1, 2,..., n, так как в этом случае при выборе строк совсем не нужно тратить время на размышления! Отражая выявленную потребность определителей, стали изучать специальные алгебраические конструкции – подстановки, причём исходное их определение использует две совершенно равноправные перестановки.
Под подстановкой понимают отображение (соответствие) множества символов, состоящего из первых n чисел: 1, 2, …, n, на себя: . Рассмотрим пример подстановки, используя две произвольные перестановки, содержащие одни и те же элементы. . ☺ ☺ Пример 3 – 01: Пусть записана подстановка: . Что это значит? Ответ: задано преобразование элементов (чисел) множества 1, 2, …, n само на себя, а именно: 1 → 6; 2 → 5; 3 → 1; 4 → 4; 5 → 2; 6 → 3; 7 → 7; 8 → 8; 9 → 9. ☻ Из примера видим, что подстановка как отображение множества чисел 1, 2, …, n не меняется при транспозиции столбцов. Для приложений, ради которых мы вводим подстановки, не важен порядок столбцов подстановки. Всегда будем предполагать эквивалентность подстановок: → , (3) где – число, в которое переходит число . ☺ ☺ Пример 3 – 02: Почему записи: и – эквивалентны? Ответ: обе подстановки определяют одно и то же преобразование элементов (чисел) множества 1, 2, …, n само на себя, а именно: 1 → 6; 2 → 5; 3 → 1; 4 → 4; 5 → 2; 6 → 3; 7 → 7; 8 → 8; 9 → 9. ☻ Из определения эквивалентности подстановок следует, что подстановки порядка различаются только нижней перестановкой элементов. Как было показано при рассмотрении элементов комбинаторики, число различных перестановок = ! Для подстановок вводят понятия: чётная подстановка и нечётная: ▫ для записи подстановки : - подстановка чётная, если четности верхней и нижней перестановок совпадают; - подстановка нечётная, если четности её верхней и нижней перестановок противоположны. ▫ для записи подстановки : - подстановка чётная, если ее определяет четная перестановка нижней строки; - подстановка нечётная, если ее определяет нечетная перестановка нижней строки. ☺ ☺ Пример 3 – 03: Определим чётность заданной подстановки: . Решение: Четность подстановки определяется числом инверсий в нижней ее строке (перестановке). Для подсчета числа инверсий перестановки воспользуемся таблицей, в которой: - символом ☻ отмечается исследуемый элемент; - символом ♦ отмечается элемент, по отношению к которому исследуемый элемент нарушает порядок: составляет инверсию.
Так как число 5 нечетное, то нижняя перестановка, значит и подстановка, нечетная. ☻ Кроме подсчета числа инверсий в перестановках для определения четности подстановок применяют также разложение их в циклы. Воспользуемся этим приемом (не обосновывая его, примем на веру!), рассмотрев конкретный пример. ☺ ☺ Пример 3 – 03: Определим чётность подстановки , используя разложение её в произведение циклов. Решение: Для иллюстрации правила формирования произвольных циклов покажем один из них, начинающийся с первого элемента верхней строки подстановки:
На этой схеме из последовательности выделен один цикл: (1 → 6 → 3 → 1). Запись цикла в разложении подстановки записывают в виде: (1, 6, 3), не повторяя второй раз элемент начала цикла. Полное разложение подстановки в произведение циклов для рассматриваемого примера принимает вид: = , где остающиеся на месте элементы отмечены скобками: (4), (7), (8), (9). Имея разложение подстановки в циклы, определим число декремент: d = n – s, где n – порядок подстановки, s – число циклов в разложении подстановки. В рассматриваемом примере: d = 9 – 6 = 3 – нечетное число → подстановка нечетная. Ответ: подстановка четная. Пример 3 – 04: Имеется запись подстановки в циклах: , найти запись этой подстановки в выражении с двумя перестановками. Решение: Используя правила построения циклов подстановки: 1) Запишем верхнюю строку подстановки: (1 2 3 4 5). 2) Отразим в нижней строке подстановки каждый из циклов: ▫ цикл: (1 3) → (1 → 3 → 1) → (3 ● 1 ● ●); ▫ цикл: (2 5) → (2 → 5 → 2) → (● 5 ● ● 2); ▫ цикл: (4) → (4 → 4) → (● ● ● 4 ●). 2) Подстановка принимает вид: Ответ: . ☻ Наблюдения: 1) Как только записан один из членов определителя: · ·…· , можно записать однозначно определяемую им подстановку. 2) При выборе члена определителя однозначно определяется чётность подстановки → вопрос: А не зависит ли знак члена определителя от чётности подстановки? Проверим гипотезу на примере определителя 3-го порядка, используя схему его вычисления в соответствии с определением: = + + – – – , Схема проверки гипотезы: ▫ для каждого члена определителя записываем соответствующую подстановку; ▫ вычисляем чётность подстановки; ▫ сопоставляем чётность-нечётность подстановки со знаками - выделенного члена определителя. A1: → : число инверсий в подстановке =0 → подстановка чётная → . A2: → : число инверсий в подстановке =2 → подстановка чётная → . A3: → : число инверсий в подстановке =2 → подстановка чётная → . A4: → : число инверсий в подстановке =3 → подстановка нечётная → . A5: → : число инверсий в подстановке =1 → подстановка нечётная → . A6: → : число инверсий в подстановке =1 → подстановка нечётная → . Выводы: 1) Знак члена определителя и чётность соответствующей ему подстановки взаимно однозначно соответствуют друг другу. 2) Членов определителя , столько же подстановок. 3) Среди членов определителя: отрицательных членов столько же, сколько положительных; среди подстановок нечётных столько же, сколько чётных.
|