Комбинаторика.
Комбинаторика — это раздел математики, который занимается подсчётом количества вариантов, способов сделать что-либо. Мы будем подсчитывать это количество, перечисляя все различные варианты, то есть путём перебора вариантов. При этом важно никакой вариант не потерять и не учитывать лишние повторяющиеся варианты.
Рассмотрим задачу.
Задача 1.
У Светы в наборе есть зеленые и оранжевые кубики. Она строит башни из двух кубиков. Сколько разных башенок Света может построить?
Решение.
Переберём все варианты башен из двух кубиков:
Получается 4 разных башенки.
Ответ: 4 башенки.
В задачах, где нам надо перебрать и посчитать все варианты, важно придумать, в каком порядке их перебирать так, чтобы ничего не пропустить. Рассмотрим пример.
Задача 2.
У Миши есть красный и жёлтый фломастеры и раскраска с одинаковыми человечками. Каждый предмет костюма человечка — кепку, кофту и брюки — Миша раскрашивает одним цветом (то есть не раскрашивает, например, брюки в красно-жёлтую полоску) и хочет, чтобы человечки отличались друг от друга. Сколько разных человечков получится у Миши?
Решение.
Попробуем раскрасить человечков так, как это делает Миша, и посчитать количество вариантов раскраски.
Если красить наугад, то легко запутаться. Придумаем, в каком порядке мы будем это делать, чтобы никакой вариант раскраски не пропустить.
Пусть сначала мы будем красить кепки только красным:
Если кофту раскрашивать красным, то брюки могут быть красными или жёлтыми. То же самое и с жёлтой кофтой:
А теперь все то же самое с желтой шапкой:
Получается всего 8 разных вариантов раскраски.
Ответ: 8 разных человечков.
Задача 3.
Из города А в город Б ведут 2 дороги. Из города Б в город В — 3 дороги. И одна дорога ведёт из города А в город В. Сколько существует разных путей из А в В?
Решение.
Нарисуем схему.
Один путь – это прямой путь из города А в город В (отмечен фиолетовым цветом):
Посчитаем, сколько разных путей ведёт из города А в город В через город Б.
Если из А в Б мы идём по синей дороге, то у нас есть 3 варианта пути в В: синий-красный, синий-оранжевый и синий-жёлтый.
Если из А в Б мы идём по зелёной дороге, то тоже 3 варианта: зелёный-красный, зелёный-оранжевый и зелёный-жёлтый.
Получаем, что из А в В через город Б ведут 6 разных путей. А вместе с прямым путём из А в В всего 7 разных путей.
Ответ: 7 путей.
Перебор вариантов помог нам решить предыдущие задачи, но часто вариантов в задаче так много, что перебрать их все очень сложно. Поэтому постепенно переходим от перебора вариантов к рассуждениям и соответствующим вычислениям.
Задача 4.
У Миши есть 5 кубиков разных цветов (по 1 кубику каждого цвета). Сколько разных башенок из 2 кубиков он может построить?
Решение.
Первый кубик Миша может выбрать 5 способами – любой из 5 имеющихся у него кубиков.
После того, как он уже выбрал 1 кубик, их осталось только 4.
Значит, для любого из 5 первых кубиков он может выбрать 4 варианта второго:
Всего получаем 5*4=20 вариантов башенок.
Ответ: 20 башенок.
Задача 5.
У Лизы есть паровозик с 4 вагонами и 4 игрушки: мишка, собачка, кошка и заяц. Сколькими способами она может рассадить игрушки по вагонами?
Решение.
Пассажира для первого вагона Лиза может выбрать 4 способами – любую из имеющихся у нее игрушек.
Для второго вагона – любого из 3 оставшихся.
Для третьего вагона – любого из 2 оставшихся.
И в четвертый вагон уже сядет тот, кто останется.
Для каждого выбранного пассажира первого вагона способы размещения остальных пассажиров можно изобразить в виде дерева вариантов (возможностей).
Например, если в 1-й вагон посадить мишку, то возможны такие варианты для остальных пассажиров (всего 3*2*1=6 вариантов):
Синим и красным цветами выделены 2 из 6 вариантов размещения пассажиров.
Поскольку пассажира 1-го вагона можно выбрать четырьмя способами, и для каждого их них есть 6 способов размещения остальных пассажиров, то всего получаем 4*3*2*1=24 способа.
Ответ: 24 способами.