Определение
Упорядоченный набор $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$ — длина перестановки.
Примеры:
- В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно?
Ответ$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)$ — инверсия.
В каждой перестановке можно определить число инверсий в ней, которое можно подсчитать следующим образом: для каждого числа определяют количество стоящих справа чисел, меньших данного числа, и полученные результаты суммируются.
Пример:
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.
Перестановки
Навигация (только номера заданий)
0 из 5 заданий окончено
Вопросы:
- 1
- 2
- 3
- 4
- 5
Информация
Тест на знание темы «Перестановки»
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается...
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Результаты
Правильных ответов: 0 из 5
Ваше время:
Время вышло
Вы набрали 0 из 0 баллов (0)
Средний результат |
|
Ваш результат |
|
Рубрики
- Нет рубрики 0%
- Алгебра 0%
- 1
- 2
- 3
- 4
- 5
- С ответом
- С отметкой о просмотре
-
Задание 1 из 5
1.
Количество баллов: 1Сколькими способами могут разместиться за круглым столом 5 человек?
Правильно
Неправильно
-
Задание 2 из 5
2.
Количество баллов: 1У каких перестановок число инверсий совпадает?
Правильно
Неправильно
-
Задание 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 элементов этого множества.
Правильно
Неправильно
Таблица лучших: Перестановки
Место | Имя | Записано | Баллы | Результат |
---|---|---|---|---|
Таблица загружается | ||||
Нет данных | ||||