Комбинаторное правило умножения

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

Перечислением и подсчётом комбинаций элементов различных множеств занимается раздел математики, который называется комбинаторикой.

Слово «комбинаторика» происходит от латинского слова, которое означает «сочетать, соединять».

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

Пример. На турнире по шахматам встретились две команды. В первой команде было 4 игрока, а во второй – 5 игроков. Каждый игрок пожал руки всем игрокам из другой команды. Сколько было совершено рукопожатий?

Предположим, что каждая команда представляет собой множество. Игроки команды – элементы этого множества.

Можно считать, что каждое рукопожатие – это пара игроков. Тогда возникает множество пар. Выясним, сколько элементов в этом множестве.

Изобразим оба множества и рукопожатия с помощью графа. Синие вершины (их 4) – игроки из первой команды, зелёные вершины (их 5) – игроки из второй команды.

Каждая из 4 синих вершин будет связана с 5 зелёными вершинами, то есть из каждой синей вершины будет исходить ровно 5 рёбер. Всего синих вершин 5, а значит, всего рёбер – 20.

Получается, что если имеется множество А, в котором 4 элемента, и множество В, в котором 5 элементов, то можно составить множество пар.

В каждой паре сначала записан какой-то элемент множества А, а потом – какой-то элемент множества В. То есть пары упорядоченные. Всего таких пар в данном примере 20.

Множества А и В могут иметь и другое количество элементов.

Пусть во множестве А всего n элементов, а во множестве B всего k элементов. Тогда множество упорядоченных пар состоит из nk элементов.

Комбинаторное правило умножения.

Пример. Предположим, что есть белый хлеб, чёрный хлеб, сыр, колбаса и варенье. Сколько разных бутербродов (хлеб и что-то одно сверху) можно приготовить?

Всего получается 6 разных бутербродов.

Ответить на данный вопрос можно было и с помощью комбинаторного правила умножения.

У нас 2 вида хлеба и 3 вида дополнений к нему. Умножив 2 на 3, получим, что можно приготовить 6ь разных бутербродов.

Пример. В классе 13 мальчиков и 12 девочек. Нужно выбрать двух дежурных по классу. Сколькими способами это можно сделать при условии, что пару дежурных обязательно должны составить мальчик и девочка?

Пусть мальчики представляют собой множество, в котором 13 элементов, а девочки – множество, в котором 12 элементов. Тогда по сформулированному выше правилу существует 13 умножить на 12, то есть 156 способов выбрать двух дежурных по классу так, чтобы пару составляли мальчик и девочка.

Следует отметить, что такое же правило действует, если имеются предметы трёх или более типов.

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

Пример. Пересчитаем государственные регистрационные автомобильные номера в Новосибирской области.

Государственные регистрационные автомобильные номера состоят из буквы, трёх цифр, ещё двух букв. и номера региона. Буквы и цифры могут повторяться. При этом буквы берутся не всякие. Можно использовать только 12 букв: А, В, Е, К, М, Н, О, Р, С, Т, У, Х. Цифры можно брать любые – от 0 до 9. Номер региона в Новосибирской области может быть 54 или 154.

Сколько всего можно составить регистрационных номеров для автомобилей в Новосибирской области?

Первой будет одна из 12 букв. Затем будет одна из 10 цифр. Потом снова одна из 10 цифр. И ещё одна из 10 цифр. Далее будут 2 буквы подряд. Каждая выбирается из 12 разрешённых букв. И наконец, номер региона. Он может оказаться 1 из 2.

Получается, что для автомобилей в Новосибирской области всего можно составить 3 456 000 регистрационных номеров.

Отметим, что номер региона не присваивается произвольно. Сначала всем новосибирским автомобилям присваивали номер 54, так как Новосибирская область является 54-м субъектом Российской Федерации. Когда все эти номера были исчерпаны, стали давать номер 154. Возможно скоро потребуются и другие номера.

Выполним несколько заданий.

Задание первое. Сколько можно составить пар, выбирая: а) первый предмет из 7, а второй из 9 предметов; б) первый предмет из 15, а второй из оставшихся после выбора первого предмета?

Задание второе. Сколько можно составить троек, выбирая: а) первый предмет из 7, второй из 5, а третий из 10 предметов; б) первый предмет из 9, а второй и третий из оставшихся после выбора предыдущих?

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

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

До встречи на следующих занятиях!