Комбинаторные задачи

Комбинаторика – это раздел математики, в котором изучаются все возможные способы перестановки цифр, предметов, элементов чего-либо.

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

Сегодня мы рассмотрим некоторые комбинаторные задачи.

Первая задача. Для начинки пирога бабушка решила смешать 2 продукта. У неё есть зелень, грибы, картофель и мясо. Сколько различных пирогов может испечь бабушка?

Решение. Решим эту задачу перебором всех возможных вариантов начинок. Обозначим каждую начинку буквой: зелень – З, грибы – Г, картофель – КА, мясо – М.

Теперь будем составлять начинки из двух продуктов.

Ну, а теперь давайте сосчитаем, сколько начинок получилось.

Получается, что из 4 продуктов можно сделать 6 начинок, если смешивать по 2 продукта.

Следовательно, если бабушка будет смешивать для начинки пирога 2 продукта, то у неё получится испечь 6 разных пирогов.

Ответ: бабушка может испечь  разных пирогов.

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

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

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

Картофель, кроме зелени и грибов, также можно смешать с мясом.

Теперь надо сосчитать, сколько рёбер получилось у графа. Их 6. Это значит, что из 4 продуктов можно сделать 6 начинок из 2 ингредиентов.

А значит, бабушка может испечь 6 разных пирогов.

Давайте представим, что у бабушки появился ещё один ингредиент – сыр. То есть теперь у бабушки не 4 ингредиента, а 5.

Обозначим сыр буквой С. Попробуем составлять начинки из имеющихся продуктов.

Сосчитаем, сколько получилось начинок. Их 10.

Добавился только один продукт, а вариантов начинок стало на 4 больше?

Сейчас мы решили задачу методом перебора. Первую задачу решали и методом перебора, и методом графов. Но есть и ещё один способ решения таких задач.

Посмотрите на пары, которые образовались при решении второй задачи:

З   Г   К   М   С

ЗГ, ЗК, ЗМ, ЗС

ГК, ГМ, ГС

КМ, КС

МС

Начинок, в которых на первом месте стоит зелень, – 4, то есть на одну меньше количества продуктов.

Начинок, в которых на первом месте стоят грибы, на одну меньше, чем начинок, в которых на первом месте зелень, то есть 3.

Начинок, в которых на первом месте стоит картофель – ещё на одну меньше – 2.

Начинок, в которых на первом месте стоит мясо – 1.

А вот начинок, в которых на первом месте стоит сыр, нет ни одной. Ведь сыр уже был смешан со всеми продуктами…

З   Г   К   М   С

ЗГ, ЗК, ЗМ, ЗС

ГК, ГМ, ГС

КМ, КС

МС

Итак, продуктов для начинки было 5. Теперь считаем количество начинок, которые можно сделать из этих продуктов.

4 + 3 + 2 + 1 = 10

Их 10.

Давайте предположим, что у бабушки было не 5 продуктов для приготовления начинки, а 10. Значит, первое слагаемое на 1 меньше, то есть 9. К нему прибавляем все числа в порядке убывания до одного. Находим сумму. Она равна 45.

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45

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

А ещё посмотрите, как можно быстро выполнить это довольно длинное вычисление.

Складываем крайние числа: 9 и 1. Их сумма равна 10.

Следующая пара – 8 и 2. Эта сумма тоже равна 10.

7 и 3 – 10; 6 и 4 – 10. Да ещё число 5.

Итак, 10 + 10 + 10 + 10 + 5 = 45.

Это было небольшое отступление от темы нашего занятия. Давайте вернёмся к решению комбинаторных задач.

Даны три цифры – 5, 7 и 9. Сколько различных трёхзначных чисел можно составить, используя в каждом числе все 3 цифры?

Решение. При решении таких задач нужно быть внимательными, ведь можно пропустить какое-нибудь число или написать одно и то же число 2 раза.

Ответ: можно составить  различных трёхзначных чисел.

Решим такую задачу. Даны четыре цифры – 3, 5, 7 и 9. Сколько различных трёхзначных чисел можно составить, используя в каждом числе 3 разные цифры?

Решение.

Таким образом, с каждой из четырёх цифр в разряде сотен, мы составили по 6 трёхзначных чисел. Всего получилось 6 умножить на 4, то есть 24 трёхзначных числа.

6 · 4 = 24 (ч.)

Ответ: можно составить  различных трёхзначных числа.

Значит, переставляя между собой три предмета, можно получить шесть комбинаций. Но если среди цифр есть 0, то конечно чисел получится меньше.

Давайте, например, возьмём цифры 0, 3, 9. Из них можно составить двузначные числа: 30, 39, 90, 93.

Составим трёхзначные числа из этих цифр.

309, 390, 903, 930

Получается только четыре двузначных и четыре трёхзначных числа. Ведь цифра 0 не может стоять в наибольшем разряде числа.

Обратите внимание, что в задачах на составление чисел в условии говорилось, что одна и та же цифра в числе не должна повторяться. А вот если бы цифры могли повторяться, то составление всех возможных комбинаций заняло бы очень много времени.