Задачи по комбинаторике
Главный вопрос комбинаторики — «сколькими способами?». При подсчёте вариантов их перечисляют по порядку, чтобы ни один не был пропущен или повторён. Правило сложения: если A можно выбрать m способами, а B — другими n способами, то «A или B» можно выбрать m + n способами. Правило умножения: если A можно выбрать m способами, а затем B — n способами, то «A и B» можно выполнить mn способами; для последовательных шагов числа способов перемножаются. Число размещений из n элементов по k без повторений равно Aₙᵏ = n(n − 1)…(n − k + 1); с повторениями оно равно n^k. Число способов упорядочить все n элементов (перестановок) равно n! = 1 · 2 · … · n, причём 0! = 1. У n-элементного множества 2ⁿ подмножеств, так как каждый элемент либо входит в подмножество, либо нет.
| Выбор | Формула |
|---|---|
| перестановки | Pₙ = n! |
| размещения | Aₙᵏ = n!/(n − k)! |
| сочетания | Cₙᵏ = n!/(k!(n − k)!) |
В программе школьного концерта 5 номеров. Их можно расположить по порядку 5! = 120 способами. Если открывающий номер уже определён, остальные 4 можно расставить 4! = 24 способами. Правило умножения позволяет сосчитать возможности, не перечисляя их все.
Организаторы мероприятий планируют порядок программы, специалисты по безопасности оценивают, сколько возможных паролей и кодов существует, а работники логистики подсчитывают варианты маршрутов доставки.
Запишите цифры 1, 2, 3, 4 на четырёх бумажках. Не перечисляя все варианты, вычислите, сколько различных четырёхзначных чисел можно составить, используя каждую бумажку один раз (4 · 3 · 2 · 1). Затем выпишите только те, что начинаются с 1: их должна быть четвёртая часть от общего числа.
«Буквы слова»: возьмите слово, все буквы которого различны (например, KITOB). Выпишите вручную все порядки 3 из его букв и проверьте, что их 3! = 6. Затем вычислите 5! для всех пяти букв по формуле.