bulgakov

01. Перестановки: порядок и число вариантов

Как описать порядок, в котором вышли пронумерованные шары из коробки? Если шаров nn, каждый имеет номер от 11 до nn, а повторно вынуть один и тот же шар нельзя. Запись результатов по порядку и приводит нас к перестановкам.

Перестановка — это список с фиксированным порядком

Обозначим множество номеров через

Nn={1,2,…,n},n⩾1.N_n=\{1,2,\ldots,n\},\qquad n\geqslant1.

Определение 22.1. Перестановка чисел 1,2,…,n1,2,\ldots,n — это упорядоченный список

a=(i1,i2,…,in),a=(i_1,i_2,\ldots,i_n),

в котором каждое число из NnN_n встречается ровно один раз. Число iki_k стоит на kk-м месте. Например, (4,1,2,6,3,5)(4,1,2,6,3,5) и (1,2,3,4,5,6)(1,2,3,4,5,6) — перестановки чисел из N6N_6. А (4,1,2,6,3,3)(4,1,2,6,3,3) не подходит: число 33 повторено, а числа 55 нет.

Слово упорядоченный важно. Списки (1,2,3)(1,2,3) и (2,1,3)(2,1,3) содержат одни и те же числа, но это разные перестановки. Две перестановки a=(i1,…,in)a=(i_1,\ldots,i_n) и b=(j1,…,jn)b=(j_1,\ldots,j_n) равны только тогда, когда совпадают числа на каждом месте:

a=b⟺ik=jk при всех k=1,…,n.a=b\quad\Longleftrightarrow\quad i_k=j_k\ \text{при всех }k=1,\ldots,n.

Перестановка как список отвечает на вопрос «в каком порядке записаны числа?». Позже появится двухстрочная подстановка, которая отвечает на другой вопрос — «какому числу сопоставлено данное число?».

Сколько существует перестановок

Для первого места можно выбрать любое из nn чисел. После этого для второго остаётся n−1n-1 чисел, для третьего — n−2n-2 и так далее. На последнее место остаётся ровно одно число. По правилу умножения число вариантов равно

n(n−1)(n−2)⋯2⋅1=n!.n(n-1)(n-2)\cdots2\cdot1=n!.

Знак n!n! читают «nn факториал». Например, перестановок чисел 1,2,3,41,2,3,4 ровно 4!=4⋅3⋅2⋅1=244!=4\cdot3\cdot2\cdot1=24. При n=1n=1 есть один список (1)(1), что согласуется с 1!=11!=1.

Утверждение 22.1. Количество всех перестановок чисел NnN_n равно n!n!. Доказательство — последовательный выбор элементов по местам, который мы только что разобрали. Каждый возможный список получается ровно одним таким выбором, поэтому ни один вариант не потерян и ни один не посчитан дважды.

Проверь себя

  1. Сколько перестановок можно составить из чисел 1,2,3,41,2,3,4? Почему варианты не повторяются при подсчёте?
  2. Является ли (1,3,3,4)(1,3,3,4) перестановкой чисел N4N_4?
  3. Равны ли перестановки (2,1,3)(2,1,3) и (2,3,1)(2,3,1)?
Показать решение

1. 4!=4⋅3⋅2⋅1=244!=4\cdot3\cdot2\cdot1=24. Каждый выбор числа для очередного места задаёт один определённый список, поэтому при таком подсчёте повторов нет.

2. Нет: число 33 записано дважды, а число 22 отсутствует.

3. Нет: уже на втором месте стоят разные числа (11 и 33). Для равенства должны совпадать все места.

ПрактикаЗагружаем тест…