Подстановки и перестановки кратко

Обновлено: 04.07.2024

Определение 1. Перестановкой степени n называется любая упорядоченная запись натуральных чисел 1, 2, 3, . . . , n в строчку одно за другим.

Например , 2, 4, 3, 1, 5. Это перестановка пятой степени. Вообще можно говорить о перестановках не только чисел, но и объектов любой природы, но сейчас для нас наибольший интерес представляет перестановка натуральных чисел. В принципе можно каждому объекту присвоить свой номер, тогда любая перестановка объектов может быть заменена перестановкой чисел. Можно смотреть на перестановку элементов как на перестановку их номеров.

ТЕОРЕМА 1. Существует n! различных перестановок n-ой степени из n чисел.

Доказательство:

Докажем эту теорему. Рассмотрим n различных чисел a₁,a₂,a₃, . . . ,a_n. На первое место перестановки существует n способов выбора записи чисел; на второе место остаётся уже (n-1) способ выбора чисел; на третье место останется (n-2) варианта выбора и т.д., а на последнее место остаётся один единственный вариант. Тогда можем записать, что число всех перестановок n-ой степени из n элементов равно: n·(n-1)·(n-2)· . . . ·2·1=n!. Символ n! читается ЭН- факториал. Таким образом, n! означает произведение всех натуральных чисел, не превосходящих данного числа. Теорема доказана.

Определение 2 . Говорят, что в данной перестановке два числа образуют инверсию (беспорядок), если большее из чисел в данной перестановке стоит левее меньшего. В противном случае эти два числа образуют порядок .

Пример: Рассмотрим перестановку шестого порядка: 2, 5, 1, 4, 6, 3

Подсчитаем общее количество инверсий в данной перестановке. Для этого поступим следующим образом: возьмём единицу и сосчитаем ,сколько чисел стоит левее единицы:

1 – две инверсии, затем единицу вычеркнем из перестановки; теперь возьмём двойку и подсчитаем, сколько чисел стоит левее двойки; 2 – ноль инверсий; вычёркиваем двойку и принимаемся за тройку; левее тройки стоит три числа, то есть тройка даёт нам три инверсии; вычёркиваем тройку и считаем, сколько чисел будет левее четвёрки; четвёрка даёт одну инверсию, вычёркиваем четвёрку и считаем количество чисел левее пятёрки; пятёрка даёт 0 инверсий, вычёркиваем пятёрку и считаем количество инверсий, которые даёт шестёрка; шестёрка даёт 0 инверсий.

1 – две инверсии; 2 – ноль инверсий; 3 – три инверсии; 4 – одна инверсия; 5 – ноль инверсий; 6 – ноль инверсий.

Общее число инверсий ,таким образом получается шесть.

Определение 3 . Перестановка называется чётной, если общее количество инверсий есть чётное число и, соответственно, нечётной, если общее количество инверсий, содержащихся в этой перестановке , число нечётное.

Определение 4. Транспозицией называется такое преобразование перестановки, при котором какие – либо два её элемента меняются местами, а все остальные элементы остаются на своих местах.

Теорема 2 . Все n! перестановок можно записать в таком порядке, что каждая следующая будет получаться из предыдущей с помощью одной транспозиции ( такой порядок называется идеальным), при этом ни одна перестановка не встретится дважды, а начинать можно с любой перестановки. Доказательство опустим.

Следствие из теоремы 2 : из какой–либо перестановки n-ой степени можно получить любую другую перестановку n-ой степени с помощью нескольких транспозиций.

Теорема 3 . Любая транспозиция меняет чётность перестановки на противоположную.

Определение 5 . Подстановкой n-ой степени называется любое отображение множества натуральных чисел от 1 до n самого на себя.

Каждую подстановку будем записывать в две строки, предполагая, что под каждым числом записано именно то число, которое ему соответствует. Заметим, что порядок чисел в верхней строчке является несущественным, например, рассмотрим подстановку пятой степени:

Здесь и в той и в другой подстановке 1 переходит в 5; 2 переходит в 4; 3 переходит в 2; 4 переходит в 3 и 5 переходит в 1. Поэтому эти подстановки тождественные. Каждую подстановку можно записывать так, чтобы все числа в первой строке располагались в порядке возрастания. При такой записи подстановок любые две подстановки одной степени будут отличаться только перестановками во второй строке. Отсюда следует довольно простой и важный вывод : существует n! различных подстановок n – ой степени.

Определение 6 . Будем называть подстановку чётной, если общее количество инверсий, содержащихся и впервой и во второй строчках чётное число и нечётной, если общее число инверсий в двух строчках – число нечётное.

Подписывайтесь на канал в Яндекс. Дзен или на канал в телеграм "Математика не для всех" , чтобы не пропустить интересующие Вас материалы. Также есть группы в VK , Одноклассниках и Facebook : всё для математического просвещения!

Когда-то очень давно мы уже говорили о комбинаторике: о сочетаниях, размещениях и перестановках. В той статье мы заходили с позиции определения факториала, сегодня же отправной точкой нашего пути будет являться абстрактная алгебра - мощное и красивое направление современной математики, которое, к сожалению, не в той же степени всем известно, насколько широко применяется. Поехали!

Что такое перестановка

Под перестановкой в математике понимаются все возможные способы, которыми некоторые элементы можно выстроить в ряд.

Ясно, что для одного элемента такое построение будет одно. Для двух элементов, например, 1 и 2 - уже два построения (12 и 21), для трех, например 1,2,3 - уже шесть построений - 123, 132, 213, 231, 312, 321 и так далее. В общем случае количество перестановок в ряду из n элементов равно n!=1*2*3*. *n.

Что такое подстановка

Под подстановкой в математике понимают операцию, изменяющую порядок элементов в перестановке.

Запомнить различие поможет просто мнемоническое правило: перестановки - способы, подстановки - операции.

Приведу небольшой пример:

На рисунке проведена подстановка которая перевела перестановку 1234 в перестановку 3241. Однако, такая форма записи достаточно громоздкая, поэтому подстановки в математике обозначают следующим образом:

Сама подстановка не зависит от порядка записи пар "исходный элемент - новый элемент". Например, в примере выше можно элементы исходной перестановки расположить по номерам (1 в 3, 2 в 4, 3 в 2, 4 в 1), тогда перестановка запишется вот так:

Чтобы конкретнее понять, когда подстановки равны, надо запомнить два правила :

1. Области определения подстановок совпадают: т.е. подстановки содержат одни и теж элементы (в приведенном примере - это 1,2,3,4).

2. Алгоритм подстановки - один и тот же. Каждый элемент, принадлежащий совместной области определения , обе подстановки переводят в один и тот же элемент.

Еще парочка примеров:

Две перестановки ниже различны, хоть и ведут к одинаковым перестановкам.

Дело в том, что в первой подстановке цифра 4 переходит в 1, а во второй 4 переходит в 4. Таким образом, алгоритм перестановок не совпадает.

Очевидно, что перестановки выше не совпадают, так как имеют разные области определения.

Приведенная выше запись вообще не является подстановкой, так как переводит два различных элемента 1 и 4 в один и тот же элемент 4, что недопустимо.

На этом сегодня всё. Если Вы думаете, что более бесполезной и тривиальной статьи по математике никогда не читали, то Вы глубоко ошибаетесь! Перестановки и подстановки - это самые первые "кирпичики" всеобъемлющей теории групп - универсального аппарата для изучения математических объектов широчайшего класса!

Спасибо! Надеюсь, было очень интересно и познавательно! Буду рад, если Вы поддержите меня ПОДПИСКОЙ, ЛАЙКОМ или даже критическим комментарием.

Определение 3.1: Пусть – конечное множество, состоящее из различных элементов. Расположение этих элементов в определенном порядке называется перестановкой.

Теорема 3.1: Количество различных перестановок из элементов равно .

Определение 3.2: Транспозицией называется такое преобразование перестановки, при котором меняются местами какие-либо два элемента перестановки, а остальные остаются на месте.

Элементы множества могут быть перенумерованы при помощи натуральных чисел , и так как в интересующих нас вопросах природа элементов множества нас не интересует, то мы примем, что элементами множества служат сами эти числа .

Теорема 3.2: Все перестановок из элементов можно расположить в таком порядке, что каждая следующая будет получаться из предыдущей одной транспозицией, причем начинать можно с любой перестановки.

Следствие: От любой перестановки можно перейти к любой другой перестановке при помощи конечного числа транспозиций.

Определение 3.3: Говорят, что в данной перестановке из первых натуральных чисел числа и образуют инверсию, если , но стоит в этой перестановке раньше .

Определение 3.4: Перестановка называется четной, если ее числа составляют четное число инверсий, и нечетной – в противном случае.

Теорема 3.3: Всякая транспозиция меняет четность перестановки.

Теорема 3.4: Число четных перестановок равно числу нечетных перестановок из символов и равно .

Определение 3.5: Взаимно-однозначное отображение конечного множества на себя называется подстановкой.

Очевидно, что две перестановки, записанные одна под другой, задают подстановку.

Например: .

Определение 3.6: Подстановка, определяемая двумя перестанов-ками, называется четной, если четности перестановок совпадают, и нечетной – в противном случае.

Теорема 3.1: Количество различных перестановок из элементов равно .

Теорема 3.3: Всякая транспозиция меняет четность перестановки.

Теорема 3.4: Число четных перестановок равно числу нечетных перестановок из символов и равно .

Определение 3.5: Взаимно-однозначное отображение конечного множества на себя называется подстановкой.

Очевидно, что две перестановки, записанные одна под другой, задают подстановку.

Например: .

Аннотация: В данной лекции рассматриваются подстановки и перестановки. Приведены основные определения, рассмотрена транспозиция, разложение подстановок в произведение циклов с непересекающимися орбитами. Рассмотрен ряд характерных задач, доказаны основные теоремы, а также приведены задачи для самостоятельного рассмотрения

Подстановки, перестановки

Теорема 5.0.4. Множество S(U) всех биекций

$f: U\to U$

с операцией произведения (композиции) отображений gf для U \xrightarrow U" />
, , обладает следующими свойствами:

$S(U)\subseteq \mT(U)$

(Другими словами, S(U) - группа относительно операции произведения отображений; S(U) - подгруппа моноида T(U): .)

Доказательство . следует из теоремы 1.6.4 и леммы 1.8.4.

$f: U\to U$

Биекции множества U часто называются подстановками . Наиболее важный для нас случай U= , в этом случае группу S_n = S() называют группой подстановок множества из n элементов (иногда называемой симметрической группой).

Запись подстановок. Перестановки

$f\in S_n$

Если - подстановка, то рассмотрим ее каноническую запись

$\begin 1 & 2 & . & n\\ f(1) & f(2) & . & f(n) \end.$

В нижней строчке (f(1), f(2). f(n)) , поскольку f - биекция, встречаются все элементы i , , при этом только по одному разу. Такие строчки элементов (i₁. i_n) , , где каждый элемент i_j , , встречается один и только один раз, называются перестановками элементов 1,2. n .

$n!=1\cdot 2\cdot . \cdot n$

Лемма 5.1.1. Число всех перестановок (i₁. i_n) из n элементов равно .

$n\cdot (n-1)\cdot . \cdot 2\cdot 1 = n$

Доказательство. Для i₁ имеем n возможностей. При выбранном i₁ для i₂ имеем (n-1) возможность. Таким образом, число различных перестановок равно !.

Лемма 5.1.2. Число различных подстановок множества равно n ! (т. е. | S_n|=n !).

$f\in S_n$

Доказательство. Для рассмотрим каноническую запись

$f=\begin 1 & 2 & . & n\\ f(1) & f(2) & . & f(n) \end.$

Таким образом, различных подстановок столько же, сколько различных перестановок n элементов, т. е. n !.

$f\in S_n$

Во многих случаях удобно рассматривать записи подстановки , располагая в верхней строчке произвольную перестановку (i₁,i₂. i_n) :

$f = \begin i_1 & i_2 & . & i_n\\ f(i_1) & f(i_2) & . & f(i_n) \end.$

$\begin i\\ f(i) \end.$

$f = \begin 1 & 2\\ 1 & 2 \end = \begin 2 & 1\\ 2 & 1 \end.$

$f: \ Для биекции \to \$
, f(1)=2 , f(2)=1 , имеем

$f = \begin 1 & 2\\ 2 & 1 \end = \begin 2 & 1\\ 1 & 2 \end.$

$f=\begin i_1 & . & i_n\\ j_1 & . & j_n \end \in S_n,$

$f^<-1> =\begin j_1 & . & j_n\\ i_1 & . & i_n \end.$

$\begin 1 & 2 & 3\\ 2 & 1 & 3 \end \begin 1 & 2 & 3\\ 1 & 3 & 2 \end = \begin 1 & 2 & 3\\ 2 & 3 & 1 \end.$

$\begin i_1 & i_2 & . & i_n\\ j_1 & j_2 & . & j_n \end \begin 1 & 2 & . & n\\ i_1 & i_2 & . & i_n \end = \begin 1 & 2 & . & n\\ j_1 & j_2 & . & j_n \end.$

$\begin e&= \begin 1 & 2 & 3\\ 1 & 2 & 3 \end; &\qquad (1\quad 2) &= \begin 1 & 2 & 3\\ 2 & 1 & 3 \end; \\ (1\quad 3) &= \begin 1 & 2 & 3\\ 3 & 2 & 1 \end; & (2\quad 3) &= \begin 1 & 2 & 3\\ 1 & 3 & 2 \end; \\ (1\quad 2\quad 3)&= \begin 1 & 2 & 3\\ 2 & 3 & 1 \end; & (1\quad 3\quad 2)&= \begin 1 & 2 & 3\\ 3 & 1 & 2 \end. \end$

$n \geq 3$

При этом в S_n для имеем

Читайте также: