Дм3. Основы комбинаторики
Df. Комбинаторика — это раздел математики, в котором изучаются действия комбинирования над элементами множеств, а также методы исчисления множеств. К простейшим комбинаторным операциям относятся:
образование перестановок, состоящее в установлении порядка следования элементов множества друг за другом;
выборка или выделение из множества некоторой части.
В ходе комбинаторных действий над элементами первичного множества мы получаем производное множество комбинаций, в простейшем случае перестановок или выборок. Результат в исчислении производных множеств достигается использованием правил сложения, вычитания и умножения, а также выведенных из них специальных формул.
Аксиома (правило сложения). Численность суммы двух непересекающихся множеств равна сумме численностей этих множеств.
(1) .
#. В корзине 5 гладиолусов и 7 пионов. Подсчитаем количество цветков в корзине.
Множество цветов есть объединение двух непересекающихся множеств:
.
Тогда по правилу сложения искомое число равно сумме численностей классов: 5+7=12.
Следствие. Правило сложения можно распространить на произвольное количество попарно непересекающихся множеств.
Так для трех попарно непересекающихся множеств:
.
Теорема (правило вычитания). Численность дополнения множества A равна численности универсума (множества U) минус численность множества A:
(2) .
Следствие. Численность разности множеств A и B равна численности уменьшаемого множества минус численность пересечения этих множеств:
(3) .
Правило сложения удобно использовать, разбивая исчисляемое множество на классы, в которых подсчёт элементов несложен.
#. В меню столовой имеется: {первые блюда}={уха; харчо; суп овощной}, {вторые блюда}={гуляш; котлета говяжья; сосиска отварная; биточки рыбные; рыба в тесте; котлета картофельная; перец маринованный; каша манная; каша рисовая}. Узнать количество различных обедов из двух блюд, если они составляются только из мясных, либо только из рыбных, либо только из вегетарианских блюд.
Решение. Выделим классы:
C1={мясные обеды}={(харчо; y)| yV1}, где V1={гуляш; котлета говяжья; сосиска отварная};
C2={рыбные обеды}={(уха; y)| y V2}, где V2={биточки рыбные; рыба в тесте};
C3={вегетарианские обеды}={(суп овощной; y)| yV3}, где V3={котлета картофельная; перец: каша манная; каша рисовая}.
По правилу сложения
.
Теорема (правило умножения). Если при выполнении двух действий первое можно выполнить n1 способами, а затем, независимо от варианта выбора первого действия, второе действие — n2 способами, то эта упорядоченная пара действий выполняется n1n2 способами.
#3. Из пункта A в пункт B ведут 4 дороги, а из B в пункт C — 3 дороги. Сколькими различными путями можно прибыть из A в C?
Ответ: 43=12 путями.
Обозначим множество вариантов первого действия X. Пронумеруем его элементы: . Множество W различных упорядоченных пар действий вида разобьем на классы по варианту выбора первого действия:
,
,
…
.
В соответствии с условием теоремы получаем n1 классов. Число пар в каждом классе равно n2, поскольку пары одного класса различаются вариантом исполнения второго действия, а по условию теоремы их количество в каждом классе n2. К объединению классов
применимо правило сложения. Тогда численность множества W:
.
Следствие 1. Правило умножения допускает распространение на цепочки любого числа действий.
Следствие 2. Численность декартова произведения двух множеств равна произведению численностей этих множеств. Или в символической записи:
(4) .