Перестановки. Лемма о числе перестановок длины 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$ — длина перестановки.

Для $n=1$ это очевидно. Пусть утверждение верно для любого множества из $n-1$ чисел. Все перестановки из $n$ чисел можно разбить на $n$ классов, помещая в один класс лишь те перестановки, которые на первом месте имеют одно и то же число. Число перестановок в каждом классе совпадает с числом перестановок $n-1$ чисел, т. е. равно $(n-1)!$. Следовательно, число всех перестановок из $n$ чисел равно $n!$.

Примеры:

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

    $P_{n} = 7! = 5040$

    [свернуть]
  2. Сколькими способами могут разместиться за круглым столом 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$.

[свернуть]

Литература :

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

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

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


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

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

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

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