Что такое комбинаторика и где она встречается
Комбинаторика — раздел математики, который отвечает на вопрос «сколько существует вариантов». Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4. Сколькими способами пятеро друзей сядут на скамейку. Сколько существует пар из 10 человек.
Элементы комбинаторики нужны и в теории вероятностей. Чтобы найти вероятность, часто надо посчитать все исходы и благоприятные исходы, а перебирать их по одному долго. Поэтому сначала учатся считать варианты, а потом переходят к случайным событиям.
В комбинаторике почти всегда работают с конечными наборами, поэтому полезно помнить основы про множества и логику: что такое элемент, подмножество, чем отличается набор, где порядок важен, от набора, где не важен.
Правила комбинаторики: сложение и умножение
Эти два правила лежат в основе всех остальных формул. Если ты их понимаешь, многие задачи решаются без формул вообще.
Правило умножения. Если первый выбор можно сделать m способами, а второй n способами, и они независимы, то вместе их можно сделать m × n способами. В столовой 3 первых блюда, 4 вторых и 2 напитка. Полный обед можно собрать 3 × 4 × 2 = 24 способами.
Правило сложения. Если объект выбирают либо из одной группы, либо из другой, и общих элементов нет, количества складывают. В библиотеке 5 книг о космосе и 7 о море. Одну книгу на выбор можно взять 5 + 7 = 12 способами.
Простой ориентир: слова «и», «затем», «одновременно» подсказывают умножение, слово «или» подсказывает сложение.
При сложных переборах помогает дерево вариантов: из каждого выбора рисуешь ветки, и число концов веток равно числу способов.
Перестановки, размещения и сочетания: формулы комбинаторики
Сначала определение: n факториал — произведение всех натуральных чисел от 1 до n. Например, 4 факториал равен 1 × 2 × 3 × 4 = 24. Отдельно принимают, что 0 факториал равен 1.
Три основные формулы различаются тем, берут ли все элементы и важен ли порядок.
- Перестановки. Все n элементов расставляют в разном порядке. P(n) = 1 × 2 × … × n. Пять книг на полке можно расставить 120 способами.
- Размещения. Из n элементов выбирают k, и порядок важен. A(n, k) = n × (n − 1) × … × (n − k + 1), всего k множителей. Староста и его заместитель из 10 человек: A(10, 2) = 10 × 9 = 90.
- Сочетания. Из n элементов выбирают k, порядок не важен. C(n, k) = A(n, k) ÷ P(k). Два дежурных из 10 человек: C(10, 2) = 90 ÷ 2 = 45.
Сочетаний всегда не больше, чем размещений, потому что одну и ту же группу из k человек в размещениях считают k-кратно, в каждом возможном порядке. Поэтому и делят на P(k).
Сочетания C(n, k) встречаются и в испытаниях Бернулли, где считают, сколькими способами k успехов распределяются среди n попыток.
Разбор задачи: команда и должности
Задача. В классе 12 человек. Сколькими способами можно выбрать команду из 3 человек для олимпиады? Сколькими способами можно выбрать капитана, редактора и казначея? Какова вероятность, что в случайно выбранную команду попадёт Миша?
Шаг 1. Определи, важен ли порядок. В команде все равны, порядок не важен, значит нужны сочетания. Должности разные, и если поменять людей местами, получится другой результат. Значит нужны размещения.
Шаг 2. Команда. C(12, 3) = 12 × 11 × 10 ÷ (1 × 2 × 3) = 1320 ÷ 6 = 220 способов.
Шаг 3. Должности. A(12, 3) = 12 × 11 × 10 = 1320 способов. Проверка: 1320 ÷ 220 = 6, а это как раз число порядков, в которых можно расставить троих человек.
Шаг 4. Вероятность. Всех команд 220. Команд с Мишей столько, сколько способов выбрать ещё двоих из оставшихся 11: C(11, 2) = 11 × 10 ÷ 2 = 55. Вероятность равна 55 ÷ 220 = ¼.
Ответ: 220 команд, 1320 способов распределить должности, вероятность ¼.
Где ошибаются чаще всего
- Путают размещения и сочетания. Перед вычислением спроси себя, изменится ли результат, если поменять выбранные элементы местами. Если изменится, это размещения. Если нет, сочетания.
- Забывают про повторяющиеся элементы. Слово МАМА состоит из 4 букв, но разных слов из них не 24, а меньше: две буквы М и две буквы А меняются местами без изменений. Правильно: 24 ÷ (2 × 2) = 6.
- Складывают там, где нужно умножать. Если надо сделать два выбора подряд, как первое и второе блюдо, количества перемножают. Складывают только тогда, когда выбирают один раз из разных групп.
- Считают лишнее. В задачах про числа смотри на ограничения: число не может начинаться с нуля, а цифры могут не повторяться. Сначала посчитай варианты для самой ограниченной позиции.
Задачи на комбинаторику и как пользоваться страницей
Обычно в заданиях просят найти, сколько существует чисел, слов, вариантов расписания, рассадок или способов выбрать группу. Часто условие подводит к вероятности, и тогда комбинаторика нужна для подсчёта исходов.
Пока в списке выше нет решённых заданий по этой теме. Ты можешь сфотографировать своё задание и получить решение с ходом, по шагам. Когда задания появятся, сначала смотри на список: найди похожее по условию, например «сколько способов выбрать» или «сколько чисел можно составить», и сравни ход решения со своим.