04. Принцип сложения

Принцип сложения. Если элемент А можно выбрать из некоторого множества m способами, а другой элемент B – n способами, причём выборы А и В таковы, что взаимно исключают друг друга и не могут быть выбраны одновременно, то выбор какого-либо одного из этих элементов (либо А, либо В) можно осуществить (m+n) способами.

В качестве иллюстрации данного принципа рассмотрим следующий простой пример.

Пример 2.1. Пусть из города A в город B можно добраться одним авиамаршрутом, двумя железнодорожными маршрутами и тремя автобусными маршрутами. Сколькими способами можно добраться из города A в город B?

Решение. Все условия принципа сложения здесь выполнены, поэтому, в соответствии с этим принципом, получим 1+2+3=6 способов.

Рассмотрим пример, иллюстрирующий различие принципов умножения и сложения.

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

Решение. Один телевизор можно выбрать тремя способами, а магнитофон – другими двумя способами. Тогда телевизор или магнитофон можно купить 3+2=5 способов.

Во втором случае один телевизор можно выбрать тремя способами, после этого видеомагнитофон можно выбрать двумя способами. Следовательно, в силу принципа умножения, купить телевизор и видеомагнитофон можно 3×2=6 способами.

Замечание. Обычно принцип сложения применяется в тех случаях, когда в задачах встречаются союзы «или», «либо, либо» (телевизор или видеомагнитофон), а принцип умножения – в задачах, содержащих союз «и» (телевизор и видеомагнитофон).

Рассмотрим теперь примеры, в которых применяются оба правила комбинаторики: и принцип умножения, и принцип сложения.

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

Решение. Ваня может выбрать яблоко 12 способами, апельсин – 10 способами. Если Ваня выбирает яблоко, то Надя может выбрать яблоко 11 способами, а апельсин – 10 способами. Если Ваня выбирает апельсин, то Надя может выбрать яблоко 12 способами, а апельсин – 9 способами. Таким образом, Ваня и Надя могут сделать свой выбор способами.

Пример 2.4. Есть 3 письма, каждое из которых можно послать по 6 адресам. Сколькими способами это можно сделать?

Решение. В данной задаче мы должны рассмотреть три случая: а) все письма рассылаются по разным адресам, б) все письма посылаются по одному адресу, в) только два письма посылаются по одному адресу. Если все письма рассылаются по разным адресам, то число таких способов легко находится из принципа умножения: n1=6×5×4=120 способов. Если все письма посылаются по одному адресу, то таких способов будет n2=6. Таким образом, остается рассмотреть только третий случай, когда только 2 письма посылаются по одному адресу. Выбрать какое-либо письмо мы можем 3 способами и послать его по какому-либо выбранному адресу можем 6 способами. Оставшиеся два письма мы можем послать по оставшимся адресам 5 способами. Следовательно, послать только два письма по одному адресу мы можем n3=3×6×5=90 способами. Таким образом, разослать 3 письма по 6 адресам в соответствие с принципом сложения можно

N1+n2+n3 = 120+6+90 = 216 способами.

Упражнения

2.1. В урне содержится 3 синих, 5 красных и 2 белых шара. Сколькими способами можно вытащить из урны либо два белых шара, либо два цветных шара, из которых один синий, а другой – красный?

Ответ: Все шары различимы и порядок важен. Поэтому все способов .

2.2. Имеется 6 различных конвертов без марок, 4 различные марки и 3 различных конверта с марками. Сколькими способами можно выбрать конверт с маркой для отправки письма?

Ответ: .

2.3. Семья новоселов хочет приобрести письменный стол, книжный шкаф и диван. В мебельном магазине имеется 6 письменных столов, 4 книжных шкафа и 12 диванов, Кроме того, есть 2 гарнитура, содержащих письменный стол и диван, и 8 гарнитуров, содержащих книжный шкаф и письменный стол. Сколькими способами может быть сделана покупка?

Ответ: .

2.4. В букинистическом магазине лежат 6 разных изданий романа И. С. Тургенева «Рудин», 3 издания его романа «Дворянское гнездо» и 4 издания романа «Отцы и дети». Кроме того, есть 5 разных сборников, в каждом из которых есть романы «Рудин» и «Дворянское гнездо», и 7 сборников с романами «Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов?

А если в магазине есть ещё 3 сборника, содержащие романы «Рудин» и «Отцы и дети», и 5 книг, содержащих все три романа?

Решение: Можно купить либо по экземпляру каждого романа, либо сборник, содержащий два романа, и экземпляр третьего романа. Из принципов сложения и умножения получаем способа. Во втором случае можно купить ещё сборник, содержащий романы «Рудин» и «Отцы и дети», и один экземпляр «Дворянского гнезда», либо сразу все романы. Всего имеем способов.

При решении комбинаторных задач важно уметь выделять случаи, где можно использовать те или иные формулы. Пусть имеется множество, состоящее из n элементов, например, урна, содержащая n различных шаров. Выборкой будем называть любую совокупность k элементов этого множества; другими словами, выбор k шаров из урны. Однако при постановке такого эксперимента должно быть строго оговорено, каким способом производится выбор и что понимается под различными выборками.

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

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

В результате получаются четыре различные постановки эксперимента по выбору k элементов из общего числа n элементов некоторого множества.

Набор Выбор	Упорядоченный	Неупорядоченный
Без возвращений (без повторений)	Размещения	Сочетания
С возвращением (с повторениями)	Размещения с повторениями	Сочетания с повторениями

Эту таблицу для случая n=3, k=2 можно записать следующим образом:

Набор Выбор	Упорядоченный	Неупорядоченный
Без возвращений (без повторений)	(1,2) (1,3) (2,3) (2,1) (3,1) (3,2)	(1,2) (1,3) (2,3)
С возвращением (с повторениями)	(1,2) (2,1) (1,1) (1,3) (3,1) (2,2) (2,3) (3,2) (3,3)	(1,2) (1,3) (2,3) (1,1) (2,2) (3,3)

< Предыдущая		Следующая >