Перестановка из n элементов: Перестановки — урок. Алгебра, 11 класс.

Содержание

(Перестановки n элементов. Их количество. Инверсии. Четные и нечетные перестановки.)

Определение:

Перестановкой n элементов называется расположение этих элементов в определенном порядке.

Утверждение 1:

Число перестановок n элементов равно n! = 1*2*3*….*n

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

(j1,j2,…,jn)

j1 – может принимать любые значения от 1,….., n (n – штук)

j2 – может принимать любые значения из оставшихся (n-1 штук)

Всего элементов: n*(n-1)*(n-2)*….*1 = n!

Определение:

(j1,….,jk,….,jl,….,jn), jk и jl образуют инверсию, если:

  1. k < l

  2. jk > jl

Определение:

Если число инверсий в перестановке четно, то перестановка

называется четной, а если число инверсий в перестановке нечетно, то перестановка называется нечетной.

Вопрос №5: (Транспозиция. Изменение четности перестановки при транспозиции любых двух ее элементов. Количество четных и нечетных перестановок n элементов.)

Определение:

Транспозиция перестановки – это обмен местами двух ее элементов.

α = (2 4 3 1 5)

β = (2 1 3 4 5)

Данный пример показывает нам транспозицию перестановки чисел 1 и 4.

Утверждение: любая транспозиция перестановки изменяет ее четность.

Доказательство: 1) α = (j1,….,jk,jk+1,….,jn)

β = (j1,….,jk+1,jk,….,jn)

Транспозиция соседних элементов.

[β] = [α]+1, если jk < jk+1 или [β] = [α]-1, если jk > jk+1

2) α = (j1,….,jk,jk+1,….,jk+l+1,…. ,jn) — l+1 перестановка j

k с соседними элементами

-> α = (j1,….,jk+1,….,jk+l+1,jk,….,jn) — l перестановок jk+l+1 с соседними элементами -> α = (j1,….,jk+l+1,jk+1,….,jk,….,jn) – 2l+1 транспозиций соседних элементов =>

=> 2l+1 раз изменений => четность изменилась

Утверждение:

Число четных и нечетных перестановок из n элементов одинаково и равно (при n ≥ 2)

Вопрос №6: (Определитель квадратной матрицы. Вывод формулы вычисления определителя второго порядка из общего определения.)

Определение: Определителем (детерминантом)  – го порядка или определителем (детерминантом) квадратной матрицы  – го порядка называют алгебраическую сумму всех членов определителя данной матрицы, взятых со своими знаками.

Обозначение:

,

где суммирование ведется по всем перестановкам столбцов.

Вывод формулы вычисления определителя второго порядка из общего определения:

Вопрос №7: (Определитель квадратной матрицы. Вывод формулы вычисления определителя третьего порядка из общего определения.)

Определение определителя описывается в вопросе №6!

Вывод формулы вычисления определителя третьего порядка из общего определения:

Вопрос №8: (Определитель квадратной матрицы. Вывод формулы вычисления определителя верхней треугольной матрицы.)

Определение определителя описывается в вопросе №6!

Вопрос №9: (Определитель квадратной матрицы. Лемма о знаке члена определителя.)

Определение определителя описывается в вопросе №6!

Лемма о знаке члена определителя:

Пусть дана квадратная матрица  – го порядка:

.

Определение:

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

Обозначение: .

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

Т.к. число всех перестановок множества   равно  , то существует ровно   членов определителя.

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

Вопрос №10: (Определитель квадратной матрицы. Доказать свойство: определитель не изменяется при транспонировании матрицы.)

Определение определителя описывается в вопросе №6!

 Определитель не изменяется при транспонировании, это значит:

                    

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

 

   Замечание:

Следующие свойства определителей будут формулироваться только для строк. При этом из свойства 1 следует, что теми же свойствами будут обладать и столбцы.

Вопрос №11: (Определитель квадратной матрицы. Доказать свойство: определитель изменяет знак при перестановке двух его строк.)

Определение определителя описывается в вопросе №6!

При перестановке двух строк определителя он умножается на –1:

                   

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

Вопрос №12: (Определитель квадратной матрицы. Доказать свойство: при умножении строки на число определитель умножается на это число.)

Определение определителя описывается в вопросе №6!

При умножении элементов строки определителя на некоторое число весь определитель умножается на это число, это значит:

                            .

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

  

Вопрос №13: (Определитель квадратной матрицы. Доказать свойство: определитель, одна из строк которого представлена в виде суммы двух строк, является суммой двух определителей. )

Определение определителя описывается в вопросе №6!

Если каждый элемент n-го столбца или n-й строки определителя представляет собой сумму двух слагаемых, то определитель может быть представлен в виде суммы двух определителей, из которых один в n-м столбце или соответственно в n-й строке имеет первые из упомянутых слагаемых, а другой — вторые; элементы, стоящие на остальных местах, у вех трех определителей одни и те же.

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

det

Определитель является линейной функцией строк матриц стоящих на любом месте. Полилинейная функция строк.

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

Урок 27. Алгебра 9 класс ФГОС

На этом уроке ученики приступят к знакомству с элементами комбинаторики и подробнее рассмотрят перестановки. Получат формулу нахождения числа перестановок из n элементов и применят её при решении комбинаторных задач.


Конспект урока «Перестановки»

Пример.

Имеются три различные цифры: 1, 2 и 3.

Переставляя их, можно получить различные трёхзначные числа.

Если на первое место поставить цифру 1, то получим два числа: 123 и 132. Если на первое место поставить 2, то получим числа: 213 и 231. Ну, а если на первом месте окажется цифра 3, то получим числа: 312 и 321.

Каждое из этих чисел называют перестановкой из трёх элементов.

Определение:

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

Вернемся к примеру, и найдем число перестановок из трёх элементов:

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

Для выбора первого элемента существует три варианта. Для каждого из них есть два варианта выбора второго элемента. И третий элемент мы выбираем единственным способом.

Получим формулу числа перестановок из n элементов.

Пусть у нас есть n элементов. Тогда на первое место можно поставить один из них, то есть n вариантов. На второе место можно поставить любой из оставшихся n-1 элементов. На третье место можно поставить любой из оставшихся n -2 элементов. И так далее.

В результате получим такую формулу числа перестановок из

n элементов:

Расположим множители в порядке возрастания:

Для записи произведения первых n натуральных чисел, есть специальное обозначение:

Например:

Пример.

Найти число перестановок из 5 элементов:

Пример.

Найти число перестановок из 7 элементов:

Пример.

Найти число перестановок из 10 элементов:

Пример.

Определить, делится ли число 18! на 30, на 54 и на 625.

Запишем и проверим, получится ли в результате целое число:

Получили, что числитель и знаменатель дроби можно сократить на 5 и на 6. Очевидно, в результате получим целое число.

Получили, что числитель и знаменатель можно сократить на 6 и на 9. Полученное произведение равно целому числу.

Получили, что в результате сокращения в знаменателе остаётся 5. Значит число 18! не делится на 625 нацело.

Пример.

Вычислить значения выражений, содержащих факториал:

1.                Вычислить:

Представим числитель и знаменатель в виде произведения:

Теперь легко увидеть, что дробь можно сократить, вычислим:

2.                Вычислить:

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

3.                Вычислим:

Представим каждый факториал в виде произведения, вычислим:

Нашли значения выражений, содержащих знак факториала.

Пример.

Сколько 6 — ых чисел можно составить, используя цифры 1, 3, 5, 7, 8 и 9, не повторяя их?

Решение задачи сводиться к нахождению числа перестановок из 6 элементов.

Применим формулу:

Сколько 6 — ых чисел можно составить, используя цифры 0, 3, 5, 7, 8 и 9, не повторяя их?

Переставляя 6 данных цифр, мы получим 720 различных вариантов. Но ведь число не может начинаться с 0. Тогда мы должны вычесть все случаи, когда 0 записан на первом месте. На первом месте у нас 0, а остальные 5 цифр могут располагаться в любом порядке и количество таких вариантов, равно числу перестановок из 5 элементов.

Найдём количество таких случаев:

Получим:

Пример.

Имеется 9 карандашей, 4 из которых — простые. Сколькими способами можно разложить их в коробке так, чтобы все простые карандаши лежали рядом?

Будем рассматривать все простые карандаши как 1. Тогда нам нужно разложить 6 объектов. Найдём сколькими способами это можно сделать. Найдем число перестановок из 6 элементов:

В каждом из полученных способов четыре простых карандаша тоже можно разложить по-разному, получим:

Для нахождения общего числа способов:

Предыдущий урок 26 Примеры комбинаторных задач

Следующий урок 28 Размещения


Получите полный комплект видеоуроков, тестов и презентаций Алгебра 9 класс ФГОС

Чтобы добавить комментарий зарегистрируйтесь или войдите на сайт

8.

1: Перестановки — Математика LibreTexts
  1. Последнее обновление
  2. Сохранить как PDF
  • Идентификатор страницы
    285
    • Исайя Ланкхэм, Бруно Нахтергаэле и Энн Шиллинг
    • Калифорнийский университет, Дэвис

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

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

    Для данного положительного целого числа \(n \in \mathbb{Z}_{+}\) перестановка (упорядоченного) списка \(n\) различных объектов представляет собой любое переупорядочение этого список. Однако при описании самих переупорядочений природа задействованных объектов более или менее не имеет значения. Например, мы можем представить себе замену второго и третьего элементов в списке из пяти различных объектов — независимо от того, что это за элементы — и это определяет конкретную перестановку, которую можно применить к любому списку из пяти объектов.

    Поскольку природа переставляемых (т. е. переставляемых) объектов не имеет значения, обычно в качестве стандартного списка \(n\) объектов используются целые числа \(1,2,\ldots,n\). В качестве альтернативы можно рассматривать эти целые числа как метки для элементов в любом списке из \(n\) различных элементов. Это приводит к следующему определению.

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

    Перестановка \(\pi\) из \(n\) элементов является взаимно однозначной и на функцию, имеющую множество \(\{1,2,\ldots, n\ }\) как его домен, так и кодовый домен.

    Другими словами, перестановка — это функция \(\pi:\{1, 2, \ldots, n\} \longrightarrow \{1, 2, \ldots, n\}\) такая, что для каждого целого числа \(i \in \{1, \ldots, n\}\), существует ровно одно целое число \(j \in \{1, \ldots, n\}\), для которого \(\pi(j) = я\). Обычно мы будем обозначать перестановки греческими буквами, такими как \(\pi\)(pi), \(\sigma\)(sigma) и \(\tau\)(tau). Набор всех перестановок \(n\) элементов обозначается \(\mathcal{S}_{n}\) и обычно называется симметрической группой степени 9.0037 \(н\). (В частности, множество \(\mathcal{S}_{n}\) образует группу по функциональной композиции, как обсуждалось в разделе 8.1.2).

    Для данной перестановки \(\pi \in \mathcal{S}_{n}\) существует несколько общих обозначений, используемых для указания того, как \(\pi\) переставляет целые числа \(1, 2, \ldots, н\). При работе с этими различными обозначениями важно помнить, что \(\pi\) — это функция, определенная на конечном множестве \(\{1, 2, \ldots, n\}\), с используемой нотацией как удобное сокращение для отслеживания того, как \(\pi\) переставляет элементы в этом наборе.

    Определение 8.1.2: двухстрочное обозначение

    Учитывая перестановку \(\pi \in \mathcal{S}_{n}\), обозначим \(\pi_{i} = \pi(i) \) для каждого \(i \in \{1, \ldots, n\}\). Тогда двухстрочное обозначение для \(\pi\) задается матрицей \(2 \times n\)

    \[
    \pi =
    \begin{pmatrix}
    1 & 2 & \cdots & n \\
    \pi_{1} & \pi_{2} & \cdots & \pi_{n}
    \end{pmatrix}.
    \]

    Другими словами, если задана перестановка \(\pi \in \mathcal{S}_{n}\) и целое число \(i \in \{1, \ldots, n\}\), мы обозначаем образ \(i\) под \(\pi\) через \(\pi_{i}\) вместо использования более обычного обозначения функции \(\pi(i)\). Затем, чтобы указать изображение каждого целого числа \(i \in \{1, \ldots, n\}\) под \(\pi\), мы перечисляем эти изображения в двухстрочном массиве, как показано выше. (Можно также использовать так называемые однострочное обозначение для \(\pi\), которое задается простым игнорированием верхней строки и записью \(\pi = \pi_{1}\pi_{2}\cdots\pi_{n}\). )

    Важно отметить, что, хотя мы представляем перестановки в виде \(2 \x n\) матриц, вы не должны думать о перестановках как о линейных преобразованиях из \(n\)-мерного векторного пространства в двумерное -мерное векторное пространство. Более того, операция композиции перестановок, которую мы описываем в разделе 8.1.2 ниже , не .0045 соответствуют умножению матриц. Использование матричных обозначений для обозначения перестановок является просто вопросом удобства.

    Пример \(\PageIndex{3}\):

    Предположим, что у нас есть набор из пяти различных объектов и мы хотим описать перестановку, которая помещает первый элемент на вторую позицию, а второй элемент — на пятую позицию. , третий элемент на первую позицию, четвертый элемент на третью позицию и пятый элемент на четвертую позицию. Тогда, используя введенные выше обозначения, мы имеем перестановку \(\pi \in \mathcal{S}_{5}\) такую, что

    \[
    \pi_{1} = \pi(1) = 3, \quad
    \pi_{2} = \pi(2) = 1, \quad
    \pi_{3} = \pi(3) = 4, \quad
    \pi_{4} = \pi(4) = 5, \quad
    \pi_{5} = \pi(5) = 2.
    \]

    В двухстрочном представлении мы бы запишите \(\pi\) как
    \[
    \pi =
    \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    3 & 1 & 4 & 5 & 2
    \end{pmatrix}. {\rm th}\). Это доказывает следующую теорему. 9Теорема 8.1.4 }| = n\cdot(n-1)\cdot(n-2)\cdot\,\cdots\,\cdot 3\cdot 2\cdot 1
    = n!
    \]

    Мы завершаем этот раздел несколькими примерами, включая полное описание одной перестановки в \(\mathcal{S}_{1}\), двух перестановок в \(\mathcal{S}_{2 }\) и шесть перестановок в \(\mathcal{S}_{3}\). Для вашей собственной практики вы должны (терпеливо) попытаться перечислить перестановки \(4! = 24\) в \(\mathcal{S}_{4}\).

    Пример \(\PageIndex{5}\):

    1. Для любого положительного целого числа \(n \in \mathbb{Z}_{+}\) функция тождества \(\mbox{id}:\{ 1, \ldots, n\} \longrightarrow \{1, \ldots, n\}\), заданное формулой \(\mbox{id}(i) = i\), \(\forall \ i \in \{1 , \ldots, n\}\), является перестановкой в ​​\(\mathcal{S}_{n}\). Эту функцию можно рассматривать как тривиальное переупорядочение, которое вообще не меняет порядок, и поэтому мы называем ее тривиальной или тождественной перестановкой.
    2. Если \(n = 1\), то по теореме 8. 1.4 \(|\mathcal{S}_{n}| =1! = 1\). Таким образом, \(\mathcal{S}_{1}\) содержит только тождественную перестановку.
    3. Если \(n = 2\), то по теореме 8.1.4 \(|\mathcal{S}_{n}| = 2! = 2 \cdot 1 = 2\). Таким образом, существует только одна нетривиальная перестановка \(\pi\) в \(\mathcal{S}_{2}\), а именно преобразование, меняющее местами первый и второй элементы в списке. В качестве функции \(\pi(1) = 2\) и \(\pi(2) = 1\) и, в двухстрочной записи,

    \[
    \pi
    =
    \begin{pmatrix}
    1 & 2 \\
    \pi_{1} & \pi_{2}
    \end{pmatrix}
    =
    \begin{pmatrix}
    1 & 2 \\
    2 и 1
    \end{pmatrix}.
    \]

    4. Если \(n = 3\), то по теореме 8.1.4 \(|\mathcal{S}_{n}| = 3! = 3 \cdot 2 \cdot 1 = 6 \). Таким образом, в \(\mathcal{S}_{3}\) есть пять нетривиальных перестановок.

    Используя двухстрочную запись, мы имеем
    \[
    \mathcal{S}_{3}
    =
    \left\{
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \ конец {pmatrix},
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix},
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix},
    \ begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix},
    \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix},
    \begin{ pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}
    \right\}
    \]

    Имейте в виду, что каждый элемент в \(\mathcal{S}_{3}\ ) является одновременно и функцией, и операцией переупорядочивания. Например, перестановка

    \[
    \pi
    =
    \begin{pmatrix}
    1 & 2 & 3 \\
    \pi_{1} & \pi_{2} & \pi_{3}
    \end{pmatrix}
    =
    \begin{pmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix}
    \]

    может быть прочитано как определение переупорядочения, которое по отношению к исходному списку помещает второй элемент в первый позиции, третий элемент во второй позиции и первый элемент в третьей позиции. Эту перестановку с тем же успехом можно было бы идентифицировать, описывая ее действие на (упорядоченный) список букв \(a,b,c\). Другими словами,

    \[
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}
    =
    \begin{pmatrix} a & b & c \\ b & c & a \end{ pmatrix},
    \]

    независимо от того, что обозначают буквы \(a, b, c\).

    Композиция перестановок

    Пусть \(n \in \mathbb{Z}_{+}\) — натуральное число, а \(\pi,\sigma \in \mathcal{S}_{n}\) — перестановки. Тогда, поскольку \(\pi\) и \(\sigma\) являются функциями из множества \(\{1,\ldots, n\}\) в себя, мы можем скомпоновать их, чтобы получить новую функцию \( \pi \circ \sigma\) (читается как «пи после сигмы»), который принимает значения

    \[
    (\pi \circ \sigma)(1) = \pi(\sigma(1)), \quad
    (\pi \circ \sigma)(2) = \pi(\sigma(2) ), \quad
    \ldots \quad
    (\pi \circ \sigma)(n) = \pi(\sigma(n)).
    \]

    В двухстрочной записи \(\pi \circ \sigma\) можно записать как

    \[
    \begin{pmatrix}
    1 & 2 & \cdots & n \\
    \pi( \sigma(1)) & \pi(\sigma(2)) & \cdots & \pi(\sigma(n))
    \end{pmatrix}
    \mbox{ или }
    \begin{pmatrix}
    1 & 2&\cdots&n\
    \pi_{\sigma(1)} & \pi_{\sigma(2)} & \cdots & \pi_{\sigma(n)}
    \end{pmatrix}
    \mbox{или }
    \begin{pmatrix }
    1 & 2 & \cdots & n \\
    \pi_{\sigma_{1}} & \pi_{\sigma_{2}} & \cdots & \pi_{\sigma_{n}}
    \end{pmatrix }.
    \]

    Пример \(\PageIndex{6}\):

    Из \(\mathcal{S}_{3}\) предположим, что у нас есть перестановки \(\pi\) и \(\sigma \) определяется как

    \[
    \pi(1) = 2, \ \pi(2) = 3, \ \pi(3) = 1
    \sigma(1) = 1, \\sigma(2) = 3, \\sigma(3) = 2.
    \]

    Тогда обратите внимание, что

    \[
    (\pi \circ \sigma)(1 ) = \pi(\sigma(1)) = \pi(1) = 2,
    \]
    \[
    (\pi \circ \sigma)(2) = \pi(\sigma(2)) = \ pi(3) = 1,
    \]
    \[
    (\pi \circ \sigma)(3) = \pi(\sigma(3)) = \pi(2) = 3.
    \]

    In другими словами,

    \[
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}
    \circ
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ \pi(1) & \pi(3) & \pi(2) \end{pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}.
    \]

    Аналогичные вычисления (которые вы должны проверить на собственной практике) дают такие композиции, как

    \[
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}
    \ circ
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ \sigma(2) & \sigma(3) & \sigma(1) \end{pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix},
    \]

    \[
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}
    \circ
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ \sigma( 1) & \sigma(2) & \sigma(3) \end{pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix},
    \]

    и

    \[
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}
    \circ
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ \mbox{id}(2) & \mbox{id}(3) & \mbox{id}(1) \end{pmatrix}
    =
    \begin {pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}. {-1} = \ mbox{идентификатор}\). например,

    \[
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}
    \circ
    \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end {pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ \pi(3) & \pi(1) & \pi(2) \end{pmatrix}
    =
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}.
    \]

    Мы суммируем основные свойства композиции на симметрической группе в следующей теореме.

    Теорема 8.1.7 Пусть \(n \in \mathbb{Z}_{+}\) — целое положительное число. Тогда набор \(\mathcal{S}_{n}\) имеет следующие свойства :

    1. Для любых двух перестановок \(\pi, \sigma \in \mathcal{S}_{n }\), композиция \(\pi \circ \sigma \in \mathcal{S}_{n}\).
    2. (Ассоциативность композиции) Для любых трех перестановок \(\pi, \sigma, \tau \in \mathcal{S}_{n}\), \[ (\pi \circ \sigma) \circ \tau = \pi \circ (\sigma \circ \tau).\] 9{-1} \circ \pi = \mbox{id}. \]

    Другими словами, набор \(\mathcal{S}_{n}\) образует группу по композиции.

    Заметим, что композиция перестановок в общем случае некоммутативна. В частности, для \(n \geq 3\) легко найти такие перестановки \(\pi\) и \(\sigma\), что \(\pi\circ\sigma\neq \sigma\circ\pi \).

    Инверсии и знак перестановки

    Пусть \(n \in \mathbb{Z}_{+}\) — натуральное число. Тогда, учитывая перестановку \(\pi \in \mathcal{S}_{n}\), естественно спросить, насколько «не по порядку» \(\pi\) по сравнению с перестановкой тождества. Одним из методов количественной оценки этого является подсчет числа так называемых пары инверсии в \(\pi\), поскольку они описывают пары объектов, которые находятся не в порядке друг относительно друга.

    Определение 8.1.8. Пусть \(\pi \in \mathcal{S}_{n}\) будет перестановкой. Тогда пара инверсий \((i, j)\) числа \(\pi\) есть пара натуральных чисел \(i, j \in \{1, \ldots, n\}\) для которых \(i \pi(j)\). Обратите внимание, в частности, что компоненты инверсионной пары — это позиционирует , где встречаются два элемента «не по порядку».

    Пример 8.1.9. Мы классифицируем все инверсионные пары для элементов в \(\mathcal{S}_{3}\):

    • \(\mbox{id} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}\) не имеет инверсионных пар, так как ни один элемент не находится «в неправильном порядке».
    • \(\pi = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}\) имеет единственную пару инверсии \((2, 3)\), так как \(\pi( 2) = 3 > 2 = \pi(3)\).
    • \(\pi = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}\) имеет единственную пару инверсии \((1, 2)\), так как \(\pi( 1) = 2 > 1 = \pi(2)\).
    • \(\pi = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}\) имеет две пары инверсии \((1, 3)\) и \((2, 3)\), так как мы имеем, что оба \(\pi(1) = 2 > 1 = \pi(3)\) и \(\pi(2) = 3 > 1 = \pi(3)\).
    • \(\pi = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}\) имеет две пары инверсии \((1, 2)\) и \((1, 3)\), так как мы имеем, что оба \(\pi(1) = 3 > 1 = \pi(2)\) и \(\pi(1) = 3 > 2 = \pi(3)\).
    • \(\pi = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}\) имеет три пары инверсии \((1, 2)\), \((1, 3)\) и \((2, 3)\), как вы можете проверить.

    Пример \(\PageIndex{1}\): Пример 8.1.10

    В качестве другого примера, для каждого \(i, j \in \{1, \ldots, n\}\) с \(i < j \), мы определяем транспозицию \(t_{i j} \in \mathcal{S}_{n}\) как

    \[
    t_{i j}
    =
    \begin{pmatrix}
    1 & 2 & \cdots & i & \cdots & j & \cdots & n \\
    1 & 2 & \cdots & j & \cdots & i & \cdots & n \\
    \end{pmatrix}.
    \]

    Другими словами, \(t_{i j}\) — это перестановка, которая меняет местами \(i\) и \(j\), оставляя все остальные целые числа на месте. Можно проверить, что количество пар инверсий в \(t_{i j}\) точно равно \(2(j — i) — 1\). Таким образом, количество инверсий в транспозиции всегда нечетно. Например,

    \[ t_{1 3}=\begin{pmatrix}1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4\end{pmatrix} \] 9{\ # \; {\гт} \; {\rm инверсия}
    \; {\гм пар} \; {\ гм в} \; \pi} =
    \begin{cases}
    +1, & \mbox{если количество инверсий в } \pi
    \mbox{ четно} \\
    -1, & \mbox{если количество инверсий в } \pi
    \mbox{ нечетное} \\
    \end{случаи}.
    \]

    Мы называем \(\pi\) четной перестановкой , если \(\mbox{sign}(\pi) = +1\), тогда как \(\pi\) называем нечетной перестановкой если \(\mbox{sign}(\pi) = -1\).

    Пример \(\PageIndex{12}\)

    Основываясь на вычислениях в Примере 8.1.9 выше, мы имеем

    \[
    \mbox{sign}
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}
    =
    \mbox{sign}
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}
    =
    \mbox{sign}
    \begin{pmatrix} 1 & 2 & 3 \ \ 3 & 1 & 2 \end{pmatrix}
    =
    +1
    \]

    и что

    \[
    \mbox{sign}
    \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}
    =
    \mbox{sign}
    \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}
    =
    \mbox{sign}
    \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}
    =
    -1.
    \]

    Аналогично, из примера 8.1.10 следует, что любая транспозиция является нечетной перестановкой.

    Мы суммируем некоторые из самых основных свойств операции над знаком на симметрической группе в следующей теореме.

    Теорема 8.1.13.

    Пусть \(n \in \mathbb{Z}_{+}\) — целое положительное число. Затем

    1. для \(\mbox{id} \in \mathcal{S}_{n}\) тождественная перестановка , \[ \mbox{sign}(\mbox{id}) = +1. \]
    2. вместо \(t_{i j} \in \mathcal{S}_{n}\) транспозиция с \(i, j \in \{1, \ldots, n\}\) и \(я

    \begin{equation}
    \mbox{sign}(t_{i j}) = -1.
    \label{eqn:sign_transposition} \tag{8.1.1} 9{-1}) & = & \mbox{знак}(\pi).
    \label{eqn:sign_inverse} \tag{8.1.3}
    \end{eqnarray}

    4. количество четных перестановок в \(\mathcal{S}_{n}\), при \(n \geq 2\), равно \(\frac{1}{2}n!\).

    5. множество \(A_{n}\) четных перестановок в \(\mathcal{S}_{n}\) образует группу по композиции.

    Авторы

    • Исайя Ланкхэм, математический факультет Калифорнийского университета в Дэвисе
    • Бруно Нахтергаэле, математический факультет Калифорнийского университета в Дэвисе
    • Энн Шиллинг, математический факультет Калифорнийского университета в Дэвисе

    Версии этого учебника в твердом и мягком переплете доступны онлайн на сайте WorldScientific. com.


    Эта страница под названием 8.1: Permutations распространяется по незаявленной лицензии, ее авторами, ремиксами и/или кураторами являются Исайя Лэнкхэм, Бруно Нахтергаэле и Энн Шиллинг.

    1. Наверх
      • Была ли эта статья полезной?
      1. Тип изделия
        Раздел или Страница
        Автор
        Исайя Ланкхэм, Бруно Нахтергаэле и Энн Шиллинг
        Показать страницу TOC
        нет
      2. Теги
        1. четная перестановка
        2. нечетная перестановка
        3. перестановка

      Генерация всех перестановок набора в Python

      Перестановка — это расположение объектов в определенном порядке. Порядок расположения объекта очень важен. Количество перестановок в наборе из n элементов равно n!. Например, есть 2! = 2*1 = 2 перестановки {1, 2}, а именно {1, 2} и {2, 1}, и 3! = 3*2*1 = 6 перестановок {1, 2, 3}, а именно {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1} , {3, 1, 2} и {3, 2, 1}.
       

      Метод 1 (возврат)
      Мы можем использовать рекурсивное решение на основе возврата, обсуждаемое здесь.
      Метод 2 
      Идея состоит в том, чтобы один за другим извлечь все элементы, поместить их на первую позицию и повторить для оставшегося списка.

      Python3

      2

      2

      . 0608 (lst) = = 0 :

               return []

       

          

          

           if len (lst) = = 1 :

               return [lst]

       

          

          

       

           l = []

       

          

           for i in range ( len ( lst)):

              m = lst[i]

       

             

             

              remLst = lst[:i] + lst[i + 1 :]

       

             

             

              for p in permutation(remLst):

                  l. append([m] + p)

           return l

       

       

      data = list ( '123' )

      for p in permutation(data):

           печать (p)

      DEF Пермта (LST):

      Вывод:

       ['1', '2', '3']
      ['1', '3', '2']
      ['2', '1', '3']
      ['2', '3', '1']
      ['3', '1', '2']
      ['3', '2', '1'] 

      Метод 3 (прямая функция)
      Мы можем сделать это, просто используя встроенную функцию перестановки в библиотеке itertools. Это самый короткий способ найти перестановку.
       

      Python3

      from itertools import permutations

      l = list (permutations( range ( 1 , 4 )))

      печать (л)

      Вывод:

       [(1, 1, 3), (1, 2, 3) 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] 

      Эта статья предоставлена ​​ Arpit Agarwal .

      Добавить комментарий

      Ваш адрес email не будет опубликован. Обязательные поля помечены *