Урок 41. Примеры комбинаторных задач -

Конспект

Комбинаторные задачи – это задачи, в которых необходимо составить комбинации каких-либо элементов из заданного набора по определённым условиям и (или) подсчитать количество получившихся комбинаций.

Комбинаторика – раздел математики, который занимается решением комбинаторных задач.

При решении комбинаторных задач можно воспользоваться:
• методом перебора;
• деревом возможных вариантов;
• комбинаторным правилом умножения.

Рассмотрим эти способы на примерах.

Задача 1
В магазине детских игрушек Маше понравились четыре мягких игрушки: мишка, енот, лиса и белка. Мама разрешила взять только две из них. Сколько существует вариантов выбора игрушек у Маши?

Решение
Переберём все возможные варианты выбора двух игрушек.

Сначала составим все варианты, в которых одной из игрушек будет мишка. Получим три варианта:
мишка и енот
мишка и лиса
мишка и белка

Теперь составим все варианты, в которых не будет мишки, но будет енот. Получим ещё два варианта:
енот и лиса
енот и белка

Наконец составим все варианты, в которых не будет ни мишки, ни енота, но будет лиса. Такой вариант остался только один:
лиса и белка

Других вариантов выбора игрушек не осталось. Значит, у Маши всего 6 вариантов выбора игрушек.

Ответ: 6 вариантов.

Мы решили задачу методом перебора.

Задача 2
Петя, Коля и Вася решили съесть мороженое. У мальчиков было одно клубничное, одно шоколадное, одно малиновое и одно вишнёвое мороженое. Сколько вариантов выбора мороженого было у мальчиков?

Решение
Решим эту задачу с помощью дерева возможных вариантов. Обозначим клубничное мороженое буковой «к», шоколадное – «ш», малиновое – «м», вишнёвое – «в».
Поскольку мы учтём все возможные варианты, то нам всё равно, в каком порядке мальчики будут выбирать мороженое. Сначала проиллюстрируем все возможные варианты выбора Пети:

Теперь для каждого из вариантов выбора Пети проиллюстрируем все возможные варианты выбора Коли:

И наконец, для каждого из вариантов выбора Пети и Коли проиллюстрируем все возможные варианты выбора Васи:

Мы перебрали все возможные варианты. Полученная схема и называется деревом возможных вариантов. Осталось определить количество этих вариантов. Для этого нужно посчитать количество вариантов в последней строке. Получилось 24 варианта.

Ответ: 24 варианта.

Мы решили задачу с помощью дерева возможных вариантов.

Эту же задачу можно решить, не изображая схему.

Решение
Будем рассуждать следующим образом. Поскольку мы учтём все возможные варианты, то нам всё равно, в каком порядке мальчики будут выбирать мороженое.

Пусть Петя выбирает мороженое первым. У него есть 4 варианта выбора.

Если Коля выбирает вторым, то у него останется 3 варианта для каждого выбора Пети. То есть всего вариантов выбора Пети и Коли будет 4 • 3.

У Васи останется по 2 варианта для каждого из выборов Пети и Коли. Значит, всего вариантов будет 4 • 3 • 2 = 24.

Ответ: 24 варианта.

Мы решили задачу с помощью комбинаторного правила умножения. Сформулируем его для общего случая.

Пусть из некоторого набора элементов нужно выбрать последовательно k элементов. И пусть первый элемент можно выбрать n1 способами, затем второй – n2 способами из оставшихся, и т. д. Тогда количество способов, которыми могут быть выбраны все k элементов, равно n1 • n2 • … • nk.

Решим ещё одну задачу.

Задача 3
Марина, Вера и Лена решили купить по воздушному шару. У продавца было 7 шаров разных цветов: зелёный, красный, розовый, жёлтый, оранжевый, фиолетовый и синий. Сколько вариантов выбора шаров есть у девочек, учитывая, что Марина не любит зелёный цвет и не купила бы себе такой воздушный шар?

Решение
Для решения задачи воспользуемся комбинаторным правилом умножения.

Поскольку у Марины есть предпочтения по цвету шара, начнём выбор с неё. У Марины всего 6 вариантов выбора шара. Вера может выбрать любой из оставшихся шаров, т. е. у неё тоже 6 вариантов выбора шара. Тогда у Лены остаётся 5 вариантов выбора.

Используя комбинаторное правило умножения получаем, что всего вариантов выбора шаров у девочек было 6 • 6 • 5 = 180.

Ответ: 180 вариантов.