10. Размещения: nʳ и n(n−1)…(n−r+1)
Размещение — это упорядоченная выборка: мы заполняем мест по очереди. Если элементы можно повторять, на каждое место есть вариантов, и размещений . Если нельзя — на каждое следующее место вариантов на один меньше: .
Что пригодится из прошлого: правило произведения — на нём построены оба вывода; выборки — там объяснено, чем размещения с повторениями отличаются от размещений без повторений. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Размещение — это слово
Пусть — алфавит из букв. Упорядоченная -выборка из — это слово длины : на первом месте стоит какая-то буква, на втором какая-то буква и так далее. Поэтому считать размещения — значит считать слова. Различны ли буквы в слове — как раз вопрос «с повторениями или без».
Размещения с повторениями:
Начнём с алфавита и слов длины . Выберем первую букву (три способа), затем вторую (снова три способа — повторять можно):
старт
├── a ── aa ab ac
├── b ── ba bb bc
└── c ── ca cb cc
Три ветки по три слова: .
Теорема (а). Число размещений с повторениями из элементов по равно
Почему. Рассмотрим слова длины в алфавите из букв. Число таких слов совпадает с числом размещений с повторениями. На первом месте может стоять любая из букв. На втором месте тоже любая из букв: повторять можно, ограничений нет. То же для каждого следующего места. Рисуем ячейки и под каждой записываем число вариантов:
1-е 2-е r-е
┌──────┐ ┌──────┐ ┌──────┐
│ │ │ │ … │ │
└──────┘ └──────┘ └──────┘
n n n
По правилу произведения получаем ( множителей), то есть .
Для двоичного алфавита получается кодов — это в точности вывод из первой главы.
Размещения без повторений:
Возьмём пять букв и составим слова из трёх разных букв. Следим за тем, какие буквы ещё свободны:
свободные буквы → способов
шаг 1: a b c d e → 5
выбрали c
шаг 2: a b d e → 4
выбрали e
шаг 3: a b d → 3
выбрали a
слово: c e a
На первом шаге — любая из букв. На втором — любая, кроме уже выбранной: . На третьем — любая, кроме двух выбранных: . Итого слов.
Теорема (б). Число размещений без повторений из элементов по равно
Почему. Слова длины из букв, в которых буквы не повторяются, считаем по местам. Первое место: любая из букв — способов. Второе: любая, кроме первой, — способ. Третье: любая, кроме первых двух, — . Каждый раз число свободных букв на одну меньше. К -му месту уже занято букв, поэтому свободных остаётся .
Важно: какие буквы свободны, зависит от прежних выборов, но сколько их — нет. Поэтому правило произведения применимо (как с цифрами в главе про правила суммы и произведения).
Как читать произведение
В записи ровно множителей: первый — , каждый следующий на единицу меньше, последний — . Последний множитель — не , это частая ошибка. Проверим на малых :
- : один множитель — выбрать одну букву можно способами;
- : ;
- : , последний множитель .
Сравнение двух видов
Для алфавита из пяти букв ():
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 1 | 5 | 20 | 60 | 120 | 120 | 0 | |
| 1 | 5 | 25 | 125 | 625 | 3125 | 15625 |
Что видно в таблице:
- при размещение единственное — пустое слово;
- : когда мест столько же, сколько букв, получается число перестановок — об этом следующая глава;
- при без повторений слов нет: в произведении появляется нулевой множитель, ведь свободных букв не осталось;
- при слов с повторениями строго больше, чем без повторений (при и числа совпадают, это видно в таблице). Разница при — слова вроде : их ровно , и (это диагональ таблицы из главы про виды выборок).
Примеры
1. Код из четырёх цифр. Повторять можно: кодов. Если все цифры различны: .
2. Призовая тройка. Восемь бегунов; золото, серебро и бронза — три разные награды, поэтому порядок важен, а один человек не может получить две награды. способов.
3. Флаг из трёх горизонтальных полос. Есть пять красок. Если цвета полос могут совпадать, флагов . Если все три полосы разного цвета, .
4. Слова из разных букв. Сколько существует слов из четырёх различных букв русского алфавита (в нём буквы), не обязательно осмысленных? .
Частые ошибки
- вместо . Основание — число вариантов для одного места, показатель — число мест. Двухбуквенных слов из трёх букв , а трёхбуквенных слов из двух букв .
- Последний множитель вместо . В ровно множителей.
- Забыть, что при без повторений слов нет.
- Считать «без повторений» эквивалентным «порядок не важен». Это два разных вопроса: у размещений порядок важен всегда; повторения разрешены или нет — отдельное условие.
Проверь себя
1. Сколько существует двоичных слов длины ?
Решение
Алфавит : , , повторения разрешены. .
2. Сколько существует трёхбуквенных слов с различными буквами в латинском алфавите ( букв)?
Решение
Повторений нет: .
3. В турнире участвуют десять команд. Сколькими способами можно распределить первое, второе и третье места?
Решение
Места различны, одна команда не может занять два места: .
4. Вычислите , и .
Решение
. . У восемь множителей, последний равен , поэтому : из семи букв нельзя составить слово из восьми разных.
Итог
- Размещение — слово длины в алфавите из букв.
- С повторениями: на каждое место вариантов, всего .
- Без повторений: , всего — ровно множителей.
- При размещений без повторений нет; при получается .
