bulgakov

11. Перестановки и факториал

Перестановка — это расстановка всех nn различных элементов в один ряд. Первым можно поставить любой из nn, вторым — любой из оставшихся n−1n-1, и так до последнего: всего n!=n(n−1)⋯2⋅1n!=n(n-1)\cdots2\cdot1 способов.

Что пригодится из прошлого: размещения без повторений — перестановка есть их частный случай; правило произведения. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Три книги на полке

Три разные книги a,b,ca,b,c нужно поставить на полку в ряд. Выпишем все порядки, выбирая по очереди: сначала книгу на первое место, затем на второе, затем на третье.

Схема
старт
├── a
│   ├── b ── c   → abc
│   └── c ── b   → acb
├── b
│   ├── a ── c   → bac
│   └── c ── a   → bca
└── c
    ├── a ── b   → cab
    └── b ── a   → cba

На первое место можно поставить любую из трёх книг. На второе — любую из двух оставшихся. На третье — единственную оставшуюся. Всего 3⋅2⋅1=63\cdot2\cdot1=6 порядков.

Определение и формула

Перестановкой nn элементов называют размещение без повторений из nn элементов по nn: использованы все элементы, каждый ровно один раз, а порядок важен. Число перестановок равно

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

Запись n!n! читается «эн факториал». Это просто сокращённое обозначение для произведения всех натуральных чисел от 11 до nn.

1!=1,2!=2⋅1=2,3!=3⋅2⋅1=6,4!=4⋅3⋅2⋅1=24.1!=1,\quad 2!=2\cdot1=2,\quad 3!=3\cdot2\cdot1=6,\quad 4!=4\cdot3\cdot2\cdot1=24.

Почему 0!=10!=1

Принято считать, что 0!=10!=1. Это не произвольное соглашение; вот четыре согласованных объяснения.

  1. Расставить ноль предметов можно ровно одним способом: ничего не делать, получится пустой ряд. А n!n! считает способы расстановки nn предметов.
  2. Закон «следующее равно число, умноженное на предыдущее». Для n≥1n\ge1 верно n!=n⋅(n−1)!n!=n\cdot(n-1)!; например, 4!=4⋅3!4!=4\cdot3!. Подставим n=1n=1: 1!=1⋅0!1!=1\cdot0!, откуда 0!=10!=1.
  3. Формула для сочетаний. Позже мы докажем, что способов выбрать rr элементов из nn равно n!r!(n−r)!\dfrac{n!}{r!(n-r)!}. Способ выбрать ноль элементов один (взять пустой набор). Подставим r=0r=0: n!0! n!\dfrac{n!}{0!\,n!}; это равно 11 только при 0!=10!=1.
  4. Единица как пустое произведение. Если перемножить ноль чисел, получится нейтральный элемент умножения — единица. Так же n0=1n^0=1.

Как быстро растёт факториал

nn 0 1 2 3 4 5 6 7 8 9 10 11 12
n!n! 1 1 2 6 24 120 720 5 040 40 320 362 880 3 628 800 39 916 800 479 001 600

Факториал растёт очень быстро. Несколько цифр:

  • 10!=3 628 80010!=3\,628\,800 — это ровно 42 суток в секундах, то есть шесть недель;
  • 20!20! — это уже 2 432 902 008 176 640 0002\,432\,902\,008\,176\,640\,000;
  • колоду из 5252 карт можно перетасовать 52!≈8,07⋅106752!\approx8{,}07\cdot10^{67} способами — это число из 68 цифр.

Связь размещений и факториалов

Так как n!=n(n−1)⋯(n−r+1)⋅(n−r)(n−r−1)⋯2⋅1n!=n(n-1)\cdots(n-r+1)\cdot(n-r)(n-r-1)\cdots2\cdot1, то после первых rr множителей остаётся (n−r)!(n-r)!:

n!=[n]r⋅(n−r)!⟹[n]r=n!(n−r)!.n!=[n]_r\cdot(n-r)!\qquad\Longrightarrow\qquad \boxed{[n]_r=\frac{n!}{(n-r)!}}.

Например, [8]3=8!5!=8⋅7⋅6⋅5!5!=8⋅7⋅6=336[8]_3=\dfrac{8!}{5!}=\dfrac{8\cdot7\cdot6\cdot5!}{5!}=8\cdot7\cdot6=336. Дробь сокращается: общий хвост 5!5! исчезает.

Приём вычисления. Не считайте большие факториалы целиком, а сокращайте: 10!8!=10⋅9=90\dfrac{10!}{8!}=10\cdot9=90.

Примеры

1. Рассадка. Пять человек садятся в ряд из пяти стульев: 5!=1205!=120 способов.

2. Числа из цифр. Из цифр 1,2,3,41,2,3,4, использованных по одному разу, получается 4!=244!=24 четырёхзначных чисел: 1234,1243,1324,…,43211234,1243,1324,\dots,4321.

3. Двое рядом. Шесть человек садятся в ряд, но AA и BB обязаны сидеть рядом. Склеим их в один «блок» [AB][AB]: теперь в ряду пять объектов, их можно расставить 5!5! способами. Внутри блока AA и BB можно поменять местами — ещё два способа. Итого 2⋅5!=2402\cdot5!=240. Каждой расстановке, где AA и BB стоят рядом, отвечает ровно одна пара «расстановка пяти объектов и порядок внутри блока» — и наоборот; поэтому ничего не потеряно и не посчитано дважды.

Частые ошибки

  • 0!=00!=0. Неверно: 0!=10!=1.
  • (n+1)!=n!+1(n+1)!=n!+1. Неверно: (n+1)!=(n+1)⋅n!(n+1)!=(n+1)\cdot n!. Например, 4!=244!=24, а 3!+1=73!+1=7.
  • (2n)!=2⋅n!(2n)!=2\cdot n!. Неверно. Для n=3n=3: 6!=7206!=720, а 2⋅3!=122\cdot3!=12.
  • Считать, что перестановка — это «что-то одно». Это любой порядок всех элементов; их n!n!, и они все разные.

Проверь себя

1. Сколькими способами можно выстроить в очередь шесть человек?

Решение

6!=7206!=720.

2. Вычислите 9!7!\dfrac{9!}{7!} и 100!98!\dfrac{100!}{98!} без калькулятора.

Решение

9!7!=9⋅8=72\dfrac{9!}{7!}=9\cdot8=72. 100!98!=100⋅99=9900\dfrac{100!}{98!}=100\cdot99=9900: всё остальное сокращается.

3. Сколькими способами можно расположить в ряд пять различных мячей — трёх красных и двух синих? (Цвет не влияет на подсчёт: все мячи разные.)

Решение

Всего пять различных мячей: 5!=1205!=120. Цвета в условии не мешают: мячи различны.

4. Покажите, что n!(n−1)!=n\dfrac{n!}{(n-1)!}=n при n≥1n\ge1.

Решение

n!=n⋅(n−1)!n!=n\cdot(n-1)!, поэтому при делении на (n−1)!(n-1)! остаётся nn.

Итог

  • Перестановка — расстановка всех nn различных элементов в ряд: n!=n(n−1)⋯2⋅1n!=n(n-1)\cdots2\cdot1.
  • 0!=10!=1: пустой ряд можно составить единственным способом.
  • [n]r=n!(n−r)![n]_r=\dfrac{n!}{(n-r)!} — размещения выражаются через факториалы.
  • Факториалы растут очень быстро; большие считайте сокращением дробей.
ПрактикаЗагружаем тест…