Пусть М – множество из  элементов: .

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

Пример. Упорядоченные наборы:

(1, 2, 3, 4, 5), (5, 2, 1, 4, 3), (2, 5, 4, 1, 3)

являются перестановками множества M, а наборы

(3, 2, 1, 5), (3, 2, 1, 4, 3), (3, 2, 6, 4, 5)

не являются перестановками множества М.

Определение. Перестановку  множества М называют начальной перестановкой.

Теорема. (О количестве перестановок.)

Существует ровно  перестановок множества из  элементов.

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

1) База индукции.

Пусть , т.е. . Очевидно, что существует единственная перестановка множества из одного элемента: (1).

2) Индукционная гипотеза.

Пусть существует ровно  перестановок множества из -го элемента: . Добавим к каждой перестановке множества А еще один элемент: n. Этот элемент можно поставить на 1-е место или 2-е или … или n-е место. Добавляя к каждой перестановке множества А элемент n на k-е место мы получаем, в соответствии с индукционным предположением,  перестановок уже множества М. Проделав это n раз при  мы получим всего  перестановок множества М, ч.т.д.

Теорема доказана.

Определение. Говорят, что пара чисел (i, j) образуют в перестановке инверсию, если , но число i находится в перестановке левее числа j.

Пример. В перестановке (2, 5, 4, 1, 3) инверсию образуют пары чисел (2, 1), (5, 4), (5, 1), (5, 3), (4, 1) и (4, 3).

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

Произвольную перестановку из  элементов обозначают так: . Здесь каждое число перестановки обозначают буквой с нижним индексом. Индекс показывает, в каком месте перестановки стоит данное число. Например, число , стоит в перестановке третьим по счету.

Число (количество) всех инверсий в перестановке  мы будем обозначать . Так, например, .

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

Пример. Перестановка (2, 5, 4, 1, 3)  четная, т.к.  – четное число, а перестановка  – нечетная, т.к.  .

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

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

Пример. .