18. Итог раздела: какую формулу выбрать
Почти любая задача на подсчёт решается тремя вопросами: что именно считаем (слово, набор, раздачу), важен ли порядок и можно ли повторять. Ответы выбирают формулу; если есть ограничения, задача разбивается на шаги и случаи.
Что пригодится из прошлого: всё предыдущее: правила суммы и произведения, виды выборок, размещения, перестановки, перестановки с повторяющимися элементами, сочетания, сочетания с повторениями, число решений уравнения. Эта глава ничего не добавляет к теории: она собирает формулы в одну схему и тренирует главное умение — выбирать нужную.
Схема выбора
Что считаем?
│
├─ ВСЕ N элементов в ряд
│ ├─ все разные
│ │ N!
│ └─ k видов: d₁, …, d_k штук
│ N! / (d₁! · … · d_k!)
│
└─ выбираем r элементов из n
Важен ли порядок?
├─ ДА (места, должности)
│ Можно ли повторять?
│ ├─ да → nʳ
│ └─ нет → n(n−1)…(n−r+1)
│
└─ НЕТ (комиссия, набор)
Можно ли повторять?
├─ да → C(n+r−1, r)
└─ нет → C(n, r)
Сводка по видам
- размещения с повторениями — ; код, пароль, слово; при , — 9;
- размещения без повторений — ; призовые места, должности; при , — 6;
- сочетания без повторений — ; комиссия, команда, лотерея; при , — 3;
- сочетания с повторениями — ; набор пирожных, раздача одинаковых предметов; при , — 6;
- перестановки — ; расстановка всех предметов;
- перестановки с повторяющимися — ; слова из букв данного слова ( — длина слова, — число разных букв).
Как действовать
- Переведите условие на язык слов. Что здесь «слово» (какая позиция что получает), что «набор» (кто вошёл, а кто нет), что «раздача» (сколько кому)?
- Задайте два вопроса: порядок важен? повторения разрешены?
- Если есть дополнительные условия, разбейте задачу. «И затем» — шаги, перемножаем. «Или» — случаи, складываем. Нарисуйте ячейки.
- Проверьте на маленьком примере. Пересчитайте формулу для двух-трёх элементов вручную — как с в главе про виды выборок.
- Проверьте на здравый смысл. Ответ — целое неотрицательное число. Сравните его с числом всех вариантов без ограничений: ответ не может быть больше.
Тренируемся выбирать
1. Восемь бегунов; нужно определить золото, серебро и бронзу.
Решение
Награды разные — порядок важен; один бегун не может получить две награды — без повторений. Размещение: .
2. Из тех же восьми бегунов нужно выбрать троих в сборную (без ролей).
Решение
Порядок не важен, повторять нельзя. Сочетание: . Это число призовых троек , делённое на : каждую сборную мы посчитали шесть раз — по числу способов раздать награды.
3. Сколько существует пятизначных кодов (цифры от до , повторять можно)?
Решение
Порядок важен, повторения разрешены: .
4. Сколько слов можно получить перестановкой букв слова «БАНАН»?
Решение
Есть одинаковые буквы: Б — , А — , Н — . .
5. В магазине четыре вида пирожных. Сколько способов купить шесть (одинаковые разрешены)?
Решение
Порядок покупки не важен, повторения разрешены: сочетание с повторениями, , : .
6. Сколько существует целых неотрицательных решений уравнения ?
Решение
Раздача одинаковых единиц трём переменным, то есть сочетание с повторениями: .
7. Из мальчиков и девочек нужно выбрать делегацию из двух мальчиков и трёх девочек.
Решение
Два шага подряд: мальчики и девочки. .
8. Пароль — четыре различные латинские буквы ( букв), порядок важен. Сколько паролей?
Решение
Размещение без повторений: .
9. В группе человек; каждый пожал руку каждому. Сколько рукопожатий?
Решение
Рукопожатие — пара людей без порядка и без повторений: .
10. Сколько существует четырёхзначных кодов (цифры –), в которых хотя бы одна цифра повторяется?
Решение
Проще посчитать противоположное событие. Всего кодов . Кодов без повторов (все цифры разные): . Значит, кодов, где хоть одна цифра повторяется,
Приём «все минус неподходящие» полезен, когда прямой подсчёт распадается на много случаев.
Частые ошибки выбора формулы
- Должности выдали, а считали сочетание. Если в условии есть слова «первый, второй, третий», «староста», «председатель», «на каждое место» — это порядок.
- Считали размещения, хотя порядок не важен. Слова «команда», «комиссия», «набор», «лотерея», «пара» — порядка нет.
- Не заметили, что можно повторять. «Купить пирожные» с одинаковыми — повторения есть; «выбрать людей» — повторений нет.
- Не разбили сложное условие. Если условий несколько, разбейте на шаги или случаи вместо поиска «волшебной формулы».
Итог
- Три вопроса: что считаем? важен ли порядок? можно ли повторять?
- Формулы: , , , , , .
- Условия «и затем» дают произведение, «или» — сумму; иногда проще посчитать противоположное.
- После ответа проверьте себя на маленьком примере.
