Основные правила комбинаторики
РАЗДЕЛ I. СЛУЧАЙНЫЕ СОБЫТИЯ И ИХ ВЕРОЯТНОСТЬ
Случай играет в мире столь большую роль, что обыкновенно я стараюсь отвести ему как можно меньше места в уверенности, что и без моей помощи он позаботится о себе.
А. Дюма
Для каждой науки существуют некоторые базовые или основные элементы, на которых строятся все остальные понятия, высказывания, утверждения. Главными элементами теории вероятностей являются случайное событие и случайная величина. Первому из этих элементов и посвящен данный раздел.
Однако, прежде чем, перейти к понятию случайного события и вероятности его появления рассмотрим один из разделов дискретной математики – комбинаторику.
Элементы и правила комбинаторики, как будет показано в дальнейшем, успешно применяются при решении ряда задач теории вероятностей. Практически все задачи, в которых определяется вероятность появления некоторого случайного события по классической формуле, используют те или иные формулы комбинаторики.
Глава 1.
Комбинаторика, ее основные понятия и
Правила
Понятие комбинаторики
В процессе своей деятельности человеку иногда приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторых действий. Сколько существует способов выбора трех человек из двадцати? Сколько существует способов составления фрагмента расписания занятий? Сколько существует способов занятия пятью претендентами пять вакантных должностей? Задачи такого типа и подобные им называются комбинаторными, а раздел математики, занимающийся их исследованием и решением, называется комбинаторикой. Комбинаторика рассматривает всевозможные соединения или комбинации эелементов.
Комбинациямиилисоединениями назовем группы, составленные из каких-либо предметов или элементов, например, букв, чисел, людей, предприятий и т.д.
Комбинаторика – это раздел математики, изучающий вопросы о том, сколько комбинаций (соединений) определенного вида можно составить из данных элементов.
Название «комбинаторика» происходит от латинского слова «combinatio», что означает соединение.
Комбинаторика широко применяется в математической логике, теории чисел, теории массового обслуживания, теории управляющих систем и вычислительной технике, а также во многих других разделах науки и техники. Особое место она занимает в теории вероятностей.
При решении ряда вероятностных задач успешно используются два основных правила комбинаторики: правило сложения и правило умножения, а также применяются ее основные понятия: размещения, перестановки и сочетания и их число.
Установим, прежде всего, два главных правила, на которых базируются многие утверждения комбинаторики.
Основные правила комбинаторики
Основными правилами комбинаторики являются правило сложения (суммы) и правило умножения (произведения).
Рассмотрим вначале правило умножения, на примере следующей задачи.
Пример 1.1. Из города А в город В можно добраться теплоходом, автобусом, самолетом или поездом. Из города В в город С можно добраться либо поездом, либо самолетом, либо автобусом. Сколькими способами можно осуществить путешествие из А в С.
Решение. Рассмотрим схему:
| А | Теплоход Автобус Самолет Поезд | В | Автобус Самолет Поезд | С |
Из А в В можно добраться четырьмя видами транспорта, т.е. четырьмя способами. Каждый из этих способов может быть использован с каждым из трех способов переезда из В в С. Отсюда легко получить, что существует 4·3=12 различных способов путешествия из А в С.
Соображения, которые были приведены при решении примера 1.1., лежат в основе следующего правила комбинаторики.
Правило умножения. Предположим, что требуется выполнить одно за другим k действий. Если первое действие можно выполнить n1 способами, второе n2 способами, третье n3 способами и так до k-го действия, которое может быть выполнено nk способами, то все k действий вместе могут быть выполнены числом способов, равным n1· n2· n3· … · nk.
Пример 1.2. В первой группе учится 20 человек, во второй – 25 человек. Для участия в конференции необходимо выбрать по одному человеку из каждой группы. Сколькими способами это можно сделать?
Решение. Из 20 учащихся первой группы может быть выбран любой, т.е. первое действие может быть совершено 20 способами. Аналогично из 25 учащихся второй группы также может быть выбран любой, т.е. второе действие может быть выполнено 25 способами. Следовательно, по правилу умножения оба действия, выбор из первой и второй групп по одному человеку, могут быть осуществлены 20·25=500 способами.
Изменим условие примера 1.2. и посмотрим, каким окажется его решение.
Пример 1.3. В первой группе учится 20 человек, во второй – 25 человек. Произвольно выбирают одного человека из какой-то группы. Сколькими разными способами это можно сделать?
Решение. Из первой группы человека можно выбрать 20 способами, из второй группы 25 способами. Всего способов 20+25=45.
При решении примера 1.3. существенным оказывается то, что оба действия (выбор человека из первой и выбор человека из второй группы) не могут быть выполнены одновременно, поскольку они взаимно исключают друг друга. В данном случае должно быть выполнено либо первое действие, либо второе, а не первое, а затем второе. Рассуждения при решении примера 1.3 лежат в основе второго правила комбинаторики.
Правило сложения. Если два действия взаимно исключают друг друга, причем одно из них может быть выполнено т1 способами, а другое т2 способами, то выполнить одно любое из этих действий можно т1+ т2 способами.
Это правило легко обобщается на любое конечное число действий.