Перестановки. Лемма о числе перестановок длины 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)$ называется нормальной. Также перестановки бывают четными и нечетными.
$A=\{ a_1,a_2,\ldots,a_n\}\to\{1,2,\ldots,n\}$ — естественный порядок.

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

Для

$n=1$ это очевидно. Пусть утверждение верно для любого множества из

$n-1$ чисел. Все перестановки из

$n$ чисел можно разбить на

$n$ классов, помещая в один класс лишь те перестановки, которые на первом месте имеют одно и то же число. Число перестановок в каждом классе совпадает с числом перестановок

$n-1$ чисел, т. е. равно

$(n-1)!$ . Следовательно, число всех перестановок из

$n$ чисел равно

$n!$ .

Примеры:

В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно?

Ответ

$P_{n} = 7! = 5040$

[свернуть]
Сколькими способами могут разместиться за круглым столом 10 человек?

Ответ

$P_n = 10! =3 62880$

[свернуть]

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

Пример:

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

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

Пример:

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

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

Решение

1) $\mathbf{4}, 5, 1, 3, 6, 2$
$4<5, 4>1, 4>3, 4<6, 4>2 \Rightarrow 3$
2) $4, \mathbf{5}, 1, 3, 6, 2$
$5>1, 5>3, 5<6, 5>2 \Rightarrow 3$
3) $4, 5, \mathbf{1}, 3, 6, 2$
$1<3, 1<6, 1<2 \Rightarrow 0$
4) $4, 5, 1, \mathbf{3}, 6, 2$
$3<6, 3>2 \Rightarrow 1$
5) $4, 5, 1, 3, \mathbf{6}, 2$
$6>2 \Rightarrow 1$
Теперь суммируя результаты получаем, число инверсий в данной перестановке равна: $3+3+0+1+1=8$ .

[свернуть]

Литература :

Воеводин В.В. Линейная алгебра. М.: Наука, 1980 — стр.123-124.
Белозёров Г.С. Конспект лекций.
Курош А.Г. Курс высшей алгебры. М.: Наука, 1968 — стр.28-36.

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

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

Задание 1 из 5

1.
Количество баллов: 1
Сколькими способами могут разместиться за круглым столом 5 человек?
Правильно

Неправильно
Задание 2 из 5

2.
Количество баллов: 1
У каких перестановок число инверсий совпадает?
- $(7, 2, 1, 5, 6, 9, 3, 4, 8)$
- $(3, 7, 5, 6, 2, 1, 9, 8, 4)$
- $(9, 7, 8, 3, 5, 4, 2, 1, 6)$
- $(5, 4, 3, 8, 2, 6, 9, 1, 7)$
Правильно

Неправильно
Задание 3 из 5

3.
Количество баллов: 1
Поставьте перестановки в порядке убывания числа инверсий:
- $(9, 7, 8, 3, 5, 4, 2, 1, 6)$
- $(6, 7, 8, 9, 3, 4, 2, 1, 5)$
- $(3, 8, 7, 6, 5, 9, 1, 4, 2)$
- $(5, 4, 3, 8, 2, 6, 9, 7, 1)$
- $(3, 7, 5, 6, 2, 1, 9, 8, 4)$
- $(7, 2, 1, 5, 6, 9, 3, 4, 8)$
Правильно

Неправильно

Задание 4 из 5

4.

Количество баллов: 1

Для каждой перестановки определите число инверсий:

Элементы сортировки

$7$
$3$
$9$
$10$

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

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

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

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

Задание 5 из 5

5.
Количество баллов: 1
Вставьте пропущенное слово:
- (Упорядоченный) набор n элементов множества назовём перестановкой n элементов этого множества.
Правильно

Неправильно

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

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

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

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

Литература :

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

Навигация (только номера заданий)

Информация

Результаты

Рубрики

1.

2.

3.

4.

Элементы сортировки

5.

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

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

Средний результат
Ваш результат