6.2 Перестановки и размещения

9 класс · Вероятность◷ 55–65 минут◇ БазаНужно знать: правило произведения, степени, действия с дробями

На финиш вышли $8$ бегунов. Судьи заполняют два документа: пьедестал (кто первый, второй и третий) и полный протокол (весь порядок от первого до восьмого).

Оба вопроса — про порядок, но ответы отличаются в тысячи раз. Вопрос урока: как считать число вариантов, когда объекты расставляют по местам, и почему такие числа растут так стремительно?

◎ После урока ты сможешь

• вычислять факториал и пользоваться соглашением 0! = 1
• находить число перестановок n различных объектов
• находить число размещений k объектов из n по местам
• решать задачи с ограничениями: закреплённое место, склеенная пара

Прогноз до вычислений

1. Полный протокол забега восьми бегунов — вариантов больше или меньше тысячи?
2. Во сколько раз, по-твоему, вариантов полного протокола больше, чем вариантов пьедестала?
3. Если бегунов станет девять, число полных протоколов вырастет на $1$, вдвое или сильнее?

Факториал

∴ Факториал

Факториалом натурального числа $n$ называют произведение всех натуральных чисел от $1$ до $n$:

$n!=1\cdot2\cdot3\cdot\ldots\cdot n.$

Дополнительно принимают $0!=1$. Это не каприз: соглашение делает верной формулу $n!=n\cdot(n-1)!$ при $n=1$ и не портит ни одну формулу главы.

Первые значения: $1!=1$, $2!=2$, $3!=6$, $4!=24$, $5!=120$, $6!=720$.

Факториал растёт быстрее любой степени. Сравни: $10!=3\,628\,800$, а $20!\approx2{,}4\cdot10^{18}$ — это больше, чем секунд прошло с начала нашей эры. Поэтому перебор вариантов «в столбик» здесь безнадёжен, а формула — нет.

Полезный приём: не вычисляй факториалы целиком, сокращай дробь.

$\frac{8!}{6!}=\frac{1\cdot2\cdot\ldots\cdot6\cdot7\cdot8}{1\cdot2\cdot\ldots\cdot6}=7\cdot8=56.$

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

∴ Число перестановок

Перестановка $n$ различных объектов — это способ расположить их все в ряд. Число перестановок обозначают $P_n$, и

$P_n=n!.$

Доказательство — правило произведения: на первое место $n$ кандидатов, на второе $n-1$, на третье $n-2$ и так далее до одного кандидата на последнее место.

Для восьми бегунов полный протокол имеет $8!=40\,320$ вариантов.

Размещения

∴ Число размещений

Размещение из $n$ объектов по $k$ — это выбор $k$ объектов из $n$ с расстановкой их по местам: порядок важен, повторов нет. Число размещений обозначают $A_n^k$, и

$A_n^k=\underbrace{n\,(n-1)\,(n-2)\cdot\ldots\cdot(n-k+1)}_{k\text{ множителей}}=\frac{n!}{(n-k)!}.$

Частные случаи: $A_n^1=n$, $A_n^0=1$ (единственный способ не выбрать ничего), $A_n^n=n!$ — размещение всех объектов и есть перестановка.

Главное в записи $A_n^k$ — $k$ множителей, идущих вниз от $n$. Для пьедестала восьми бегунов их три:

$A_8^3=8\cdot7\cdot6=336.$

Значит, полных протоколов ровно в $40\,320:336=120=5!$ раз больше: оставшиеся пять бегунов можно упорядочить $5!$ способами.

Управляемый эксперимент

Задай $n$ и $k$ и сравни три величины в таблице: $P_n$, $A_n^k$ и $C_n^k$. Пока смотри на первые две строки — третья понадобится в следующем уроке.

Лаборатория выбора

Треугольник Паскаля и три формулы подсчёта

Выбери, что считаем, задай n и k — и посмотри, где ответ живёт в треугольнике. Числа строки с номером n — это в точности C(n, 0), C(n, 1), …, C(n, n).

строка 8

Сочетания C(n, k)Размещения A(n, k)Перестановки n!

Сколько всего объектов, n 8От 1 до 12; стрелки клавиатуры меняют n на 1.

Сколько выбираем, k 3От 0 до 8: выбрать больше, чем есть, нельзя.

Вопрос: сколькими способами можно выбрать 3 предмета из 8 и расставить их по порядку?

Три величины для одних и тех же n и k

Величина	Как считается	Значение
P8 = 8!	1 · 2 · … · 8	40 320
A(8, 3)	8 · 7 · 6	336
C(8, 3)	A(8, 3) : 3!	56

=

A(8, 3) = 8 · 7 · 6 = 336.Размещение — это сочетание, объекты которого ещё и упорядочены: A(8, 3) = C(8, 3) · 3! = 56 · 6.

↺ Вернуть пример

Переключи режим на «Перестановки» и увеличивай $n$ по одному: каждый шаг умножает ответ на новое число, а не прибавляет к нему.

Буквы слова КНИГАРазбираем вместе

В слове КНИГА пять различных букв.

Сколько «слов» из всех пяти букв? Это перестановки: $P_5=5!=120$.

Сколько из них начинается с буквы А? Первое место занято, остальные четыре буквы переставляются свободно: $4!=24$.

Сколько трёхбуквенных «слов» без повторов? Это размещения: $A_5^3=5\cdot4\cdot3=60$.

Проверка связи: $A_5^3=60$, а $A_5^5=120$; отношение равно $2=2!$ — столько способов упорядочить две оставшиеся буквы.

Двое хотят сидеть рядомРазбираем вместе

Пять человек садятся в ряд на пять стульев. Двое из них — Аня и Боря — хотят оказаться соседями.

Приём «склейки». Считаем пару за один объект. Тогда объектов четыре, и их можно расставить $4!=24$ способами. Внутри склеенной пары порядок тоже свободен: Аня–Боря или Боря–Аня, это $2!=2$ способа.

По правилу произведения

$4!\cdot2!=24\cdot2=48.$

Проверка правдоподобия: всего рассадок $5!=120$, и доля «соседних» равна $\frac{48}{120}=\frac{2}{5}$. Это разумно: пара занимает одну из четырёх соседних позиций из десяти возможных пар мест, $\frac{4}{10}=\frac{2}{5}$.

Проверка понимания

Из 15 учеников выбирают старосту, его заместителя и казначея — все должности разные. Сколько вариантов?

• А. 2730
• Б. 455
• В. 3375

Типичная ошибка

! Посчитали размещения там, где порядок не нужен

Самая частая ошибка урока — применить $A_n^k$ к задаче, в которой мест нет.

«Из $10$ человек выбирают $3$ в жюри» — это не $10\cdot9\cdot8=720$. Такой подсчёт различает, кого выбрали первым, а жюри этого не различает: одна и та же тройка посчитана $3!=6$ раз. Верный ответ появится в следующем уроке.

Проверочный вопрос: если поменять двух выбранных местами, получится другой вариант? Да — размещения. Нет — что-то другое.

Вторая ошибка — вычислять факториалы целиком. Выражение $\frac{100!}{98!}$ считается устно: $99\cdot100=9900$. Ни один калькулятор для этого не нужен.

Практика

1. Вычисли $5!$, $6!$, $1!$ и $0!$.
2. Вычисли $\dfrac{8!}{6!}$ и $\dfrac{10!}{8!}$, не находя факториалы целиком.
3. Упрости выражение $\dfrac{(n+1)!}{n!}$ при натуральном $n$.
4. Сколькими способами $6$ человек могут встать в очередь?
5. Сколькими способами $4$ различные книги можно расставить на полке?
6. Из $8$ бегунов определяют призёров с распределением мест. Сколько вариантов?
7. Сколько трёхбуквенных «слов» без повторов можно составить из алфавита в $10$ букв?
8. Сколькими способами из $15$ учеников выбрать старосту, заместителя и казначея?
9. Сколько «слов» можно составить из всех букв слова КНИГА? Сколько из них начинается с буквы А?
10. Пять человек садятся в ряд. Сколько рассадок, в которых двое конкретных сидят рядом?
11. Реши уравнение $A_n^2=42$.
12. Во сколько раз $10!$ больше $8!$?

Ответы и пояснения

1. $5!=120$, $6!=720$, $1!=1$, $0!=1$ по соглашению.
2. $\dfrac{8!}{6!}=7\cdot8=56$; $\dfrac{10!}{8!}=9\cdot10=90$.
3. $\dfrac{(n+1)!}{n!}=n+1$.
4. $P_6=6!=720$.
5. $P_4=4!=24$.
6. $A_8^3=8\cdot7\cdot6=336$.
7. $A_{10}^3=10\cdot9\cdot8=720$.
8. $A_{15}^3=15\cdot14\cdot13=2730$.
9. $P_5=5!=120$; с буквы А начинается $4!=24$ «слова».
10. Склеиваем пару: $4!\cdot2!=24\cdot2=48$.
11. $A_n^2=n(n-1)=42$, то есть $n^2-n-42=0$, откуда $n=7$ или $n=-6$. Условию удовлетворяет $n=7$: число объектов отрицательным не бывает.
12. $\dfrac{10!}{8!}=9\cdot10=90$ раз.

Итог

• $n!$ — произведение всех натуральных чисел от $1$ до $n$; принято $0!=1$.
• Число перестановок $n$ различных объектов равно $P_n=n!$.
• Число размещений равно $A_n^k=n(n-1)\ldots(n-k+1)=\dfrac{n!}{(n-k)!}$ — ровно $k$ убывающих множителей.
• Размещения и перестановки применимы там, где порядок важен и повторов нет.
• Приёмы для задач с ограничениями: занять закреплённое место первым и «склеить» объекты, которые обязаны стоять рядом.

Дальше уберём порядок. Окажется, что число способов выбрать группу — это то же размещение, только поделённое на число перестановок внутри выбора.

← Правила подсчёта · Дальше: сочетания →

Закончил урок?

Отметь прогресс — регистрация не нужна.

Отметить пройденным