Перестановки и подстановки из n символов

Общее определение абстрактного векторного пространства.

V ≠ ; a, b, c є V; P-числовое поле.

Пусть: 1. Задана операция ∆, которая каждому a є V и каждому λ є P ставит в соответствие элемент λ∆a є V.

2. ∀ a,b є V задана операция □, которая каждой упорядоченной паре a,b є V ставит в соответствие единственный элемент a□b є V.

При этом выполняются 8 свойств (аксиом).

1. a□(b□c)=(a□b)□c

2. Ǝ z є V | ∀ a є V |a□z=z□a=a

3. ∀ a Ǝ n | n□a=a□n=z

4. a□b=b□a

5. (α+β)∆a=(α∆a)□(β∆a)

6. α∆(a□b)= (α∆a)□(α∆ b)

7. α∆(β∆a)= (αβ)∆a

8.1∆a=a

∀ a, b є V; α,β є P; 1 є P

Тогда множество V называется векторным пространством над полем Р, операция □=+, ∆=умножение вектора на число, z-единичный элемент=0, а его элементы-векторы.

Перестановкой чисел 1, 2,..., n называется любое расположение этих чисел в определенном порядке. В элементарной алгебре доказывается, что число всех перестановок, которые можно образовать из n чисел, равно 12...n = n!. Например, из трех чисел 1, 2, 3 можно образовать 3!=6 перестановок: 123, 132, 312, 321, 231, 213. Говорят, что в данной перестановке числа i и j составляют инверсию (беспорядок), если i>j, но i стоит в этой перестановке раньше j, то есть если большее число стоит левее меньшего.

Перестановка называется четной (или нечетной), если в ней соответственно четно (нечетно) общее число инверсий. Операция, посредством которой от одной перестановки переходят к другой, составленной из тех же n чисел, называется подстановкой n-ой степени.

Подстановка, переводящая одну перестановку в другую, записывается двумя строками в общих скобках, причем числа, занимающие одинаковые места в рассматриваемых перестановках, называются соответствующими и пишутся одно под другим. Например, символ обозначает подстановку, в которой 3 переходит в 4, 1 ® 2, 2 ® 1, 4 ® 3. Подстановка называется четной (или нечетной), если общее число инверсий в обеих строках подстановки четно (нечетно). Всякая подстановка n-ой степени может быть записана в виде ,т.е. с натуральным расположением чисел в верхней строке.

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

.

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

,

где индексы q₁, q₂,..., q_n составляют некоторую перестановку из чисел
1, 2,..., n. Число таких произведений равно числу различных перестановок из n символов, т.е. равно n!. Знак произведения равен (- 1)^q, где q - число инверсий в перестановке вторых индексов элементов.

Дата добавления: 2014-01-07