КОМБИНАТОРИКА
Задача1. Пассажир оставил свои вещи в автоматической камере хранения, но код не записал. Решил, что и так запомнит. Когда пришел забирать вещи, сообразил, что помнит только букву и последние две цифры. Найдите максимальное количество времени, которое потребуется для поиска кода? Код состоит из одной из первых десяти букв русского алфавита и 4 цифр. На набор одного кода потребуется 30 секунд.
Решение этой задачи состоит в переборе возможных вариантов выбора буквы и цифр, которые в данном случае можно найти все возможные варианты. Но если увеличить количество букв и цифр в задаче, то простым перебором вариантов задачу не решить. Если оглянуться вокруг, то можно заметить, что в разных областях нашей жизни довольно часто приходится иметь дело с поиском разного рода наборов (комбинаций) объектов: распределение работы между людьми, выбор целесообразного решения проблемы из нескольких возможных, перебор различных вариантов расположения мебели в квартире и т.д. Более того, часто нужно знать не сами комбинации, а их количество. В решении такой проблемы необходимо использовать знания из раздела математики, который называется комбинаторика.
| Комбинаторика – раздел математики, изучающий вопросы, связанные с вычислением числа различных комбинаций, которые можно составить из заданных объектов и подчиненных тем или иным условиям. |
Этот раздел дискретной математики играет важную роль в теории чисел, ТВ, мат. логике, вычисл. технике, кибернетике.
Как научная дисциплина комбинаторика сформировалась в 17 веке. Рождение комбинаторики как раздела математики связано с трудами Б.Паскаля и П.Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В.Лейбниц, Я.Бернулли и Л.Эйлер. В конце 19 в. интерес к комбинаторному анализу возродился в связи с бурным развитием вычислительной математики. Тогда и появилась современная символика.
| Задачи, решение которых связано с выяснением числа возможных вариантов, составленных из элементов некоторого множества, удовлетворяющих определенным условиям, будем называть комбинаторными. |
При решении комбинаторных задач можно использовать разные методы:
А) использование систематического перебора
Б) использование правил суммы и произведения
В) использование типа выборки для нахождения числа вариантов.
СИСТЕМАТИЧЕСКИЙ ПЕРЕБОР ВАРИАНТОВ
Задача 2. Из коробки, в которой 3 белых и два красных шара, наугад вынимаются два. Сколькими способами можно вытащить два шара?
1) кодировка
Обозначим белые шары цифрами 1,2,3; красные – буквами: а,б. Тогда возможны варианты:
| 1, 2 | 1, 3 | 2, 3 | а,б | ||
| 1, а | 1, б | 2, а | 2, б | 3, а | 3, б |
Пересчитаем их. Получили 10 способов.
2) таблица
| а | б | ||||
| 1,1 | 1,2 | 1,3 | 1а | 1б | |
| 2,1 | 2,2 | 2,3 | 2а | 2б | |
| 3,1 | 3,2 | 3,3 | 3а | 3б | |
| а | А,1 | А,2 | А,3 | аа | аб |
| б | Б,1 | Б,2 | Б,3 | аб | бб |
В таблице покрасили те клетки, где варианты повторяются или невозможны. Подсчитаем количество клеток, которые не закрашены. Их 10.
Ответ: 10 способов.
ПРАВИЛА СЛОЖЕНИЯ И УМНОЖЕНИЯ
Выделим два правила, с помощью которых будут выводиться основные формулы комбинаторики. Для облегчения понимания сначала будем рассматривать задачи.
Задача 3. В меню ресторана — шесть мясных и три рыбных блюда. Сколькими способами можно выбрать одно из блюд? (То есть, сколько существует разных выборок по одному блюду?)
Задача 4. В меню ресторана — шесть видов напитков содержат соки и три вида напитков содержат мороженое. Сколькими способами можно выбрать один из напитков?
Задачи явно различны. В первом случае естественно предположить, что мясные блюда не содержат рыбы, а рыбные — мяса (что свойственно русской кухне). Тогда блюд всего девять, и столько же способов выбрать одно. Во второй задаче не ясно, могут ли напитки одновременно содержать сок и мороженое. Если могут, то общее количество напитков — от шести до девяти.
| Правило сложения. Если объект со свойством А можно выбрать т способами, а объект со свойством В можно выбрать п способами, то выбор «либо А, либо В, но не одновременно» можно осуществить т + п способами |
.
Задача 5. В меню ресторана — шесть мясных и три рыбных блюда. Сколькими способами можно выбрать одно из блюд? (То есть, сколько существует разных выборок по одному блюду?)
Количество способов выбора меню можно найти по правилу суммы: 6 +3 = 9 (блюд)
Ответ: 9 блюд.
Задача 6. Сколько можно назвать двузначных чисел, кратных 15 или 19.
Решение.
Выпишем двузначные числа, кратные 15: 15, 30, 45, 60, 75, 90. Получили 6 чисел
Выпишем двузначные числа, кратные 21: 21, 42, 63, 84. Получили 4 числа.
Количество чисел, которые удовлетворяют условию задачи, можно найти по правилу суммы: 6 + 4 = 10 (чисел).
Ответ: 10 чисел.
Следующее правило несколько сложнее.
Задача 7. В меню ресторана — шесть мясных и три рыбных блюда. Сколькими способами можно выбрать одно рыбное и одно мясное блюдо? (То есть, сколько существует наборов по два разных блюда: одно мясное и одно рыбное?)
Выберем мясное блюдо (шесть способов). К каждому способу добавим рыбное блюдо (по три варианта). Получится 18 разных наборов по два блюда. Наборы будут отличаться одним или сразу двумя составляющими. Если начинать выбор с рыбного блюда, то число пар не изменится. Это те же пары, просчитанные другим способом.
| Правило умножения. Если объект со свойством А можно выбрать т способами, и после каждого такого выбора объект со свойством В можно выбрать п способами, то выбор пары объектов в указанном порядке можно осуществить т п способами. |
Сложность применения правила заключается в том, что по тексту задачи нам (как в задаче 6) могут быть не нужны пары в определённом порядке, ведь нет никакого различия между наборами (гуляш, селёдка), (селёдка, гуляш) на столе. Выбор в определённом порядке производится лишь для того, чтобы удобно было подсчитать общее число способов. В других задачах, где применяется правило умножения, выбранная комбинация обязательно является упорядоченным набором предметов (как говорят математики, «кортежем»).
Задача 8. В меню ресторана — девять разных блюд. Посетитель выбирает одно из блюд, а его приятель тоже одно, но не такое же. Сколько существует способов выбора двух разных блюд для двоих людей?
Выберем блюдо со свойством А (для первого). Это можно сделать девятью способами. После этого выберем блюдо для второго (свойство В). Это можно сделать восемью способами, чтобы избежать повторения. Всего получим 72 способа выбрать пару блюд в определённом порядке: для первого и для второго посетителей. При этом способы, когда первый ест гуляш, второй — селёдку; и первый ест селёдку, второй — гуляш, считаются разными. Ответ: 72 способа.
Если же нас интересует только то, что будет стоять на столе (например, каждый попробует оба блюда), то способов будет в два раза меньше, так как варианты (гуляш, селёдка) и (селёдка, гуляш) дают один и тот же результат. И здесь совсем другая комбинаторная ситуация.
Итак, важное условие: при решении задач с помощью правила умножения находим количество упорядоченных наборов. Иногда бывают случаи, когда приходится составлять упорядоченные наборы из трёх и более объектов. Тогда их составляют, выбирая объекты один за другим, а числа способов выбора перемножают.