Перестановки. Лемма о числе перестановок длины n

A=\{ a_1,a_2,\ldots,a_n\}\to\{1,2,\ldots,n\} — естественный порядок.

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

Упорядоченный набор n элементов множества назовём перестановкой n элементов этого множества.
(i_1,i_2,\ldots,i_n), i_j \in \{1,2,\ldots,k\}, j=\overline{1,n}. Перестановка (1,2,\ldots,n) называется нормальной. Так же перестановки бывают четными и нечетными.

Лемма о числе перестановок длины n :

Число перестановок n-элементов множества равна n!, где n — длина перестановки.

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

Примеры:

  1. В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно?
    Ответ: P_{n}=7!=5040
  2. Сколькими способами могут разместиться за круглым столом 10 человек?
    Ответ: P_n=10!=362880

Два числа i и j образуют инверсию, если i>j, но i стоит в перестановке раньше j.

Пример:

(1, 2, 3, 4, 5, 6) — нормальная перестановка.

(1, 2, 4, 5, 3, 6) — инверсия.

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

Рассмотрим на примере:

Определите число инверсий в данной перестановке:
(4, 5, 1, 3, 6, 2).

Решение показать

Литература :

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

Тест на знание темы «Перестановки»


Таблица лучших: Перестановки

максимум из 5 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных

 

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

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