Правило суммы произведения

Обозначим число элементов конечного множества А символом n(A). Если множества А и В не пересекаются, то n(АВ)=n(A)+n(B). Если множества А и В пересекаются, то n(АВ)=n(A)+n(B) – n(AB).

Например. На тарелке лежат 11 груш и 5 лимонов. Сколькими способами можно выбрать один плод?

Речь идет о выборе «яблоко или груша» из множества плодов. Поэтому используем правило суммы: 11+5=16. Значит, один плод можно выбрать 16 способами.

Правило подсчета числа элементов объединения непересекающихся конечных множеств носит название в комбинаторике правила суммы: если элемент х можно выбрать k способами, а элемент y – m способами, причем ни один из способов выбора элемента х не совпадает со способом выбора элемента y, то выбор «х или y» можно осуществить k+m способами.

Правило суммы распространяется не только на два множества. Так, например, пусть даны непересекающиеся множества А, В, С. Тогда

n(ABC)=n(A)+n(B)+n(C)-n(AB)-n(BC)-n(AC)+n(ABC).

Число элементов декартова произведения множеств А и В подсчитывается по формуле n(AB)=n(A)n(B).

Найдем сколько элементов содержит  декартово  произведение АА, если А={a, b, c, d, e}?

Так как множество А содержит 5 элементов (n(A)=5)), то декартово произведение  АА содержит 55 элементов: n(АА) = 55= 25 пар. Значит, декартово произведение АА содержит 25 элементов.     

Правило подсчета числа элементов декартова произведения конечных множеств носит название в комбинаторике правила произведения: если элемент х можно выбрать k способами, а элемент y – m способами, то пару (x, y) можно выбрать km способами.

Правила суммы и произведения могут быть обобщены на случай         n множеств.

Приведем решения некоторых комбинаторных задач:

Задача 2. В группе 30 студентов. 20 изучают немецкий язык по скайпу, 15 – изучают английский язык по скайпу. Каким может быть число студентов, изучающих оба языка; изучающих хотя бы один язык?

Решение: обозначим множество студентов, изучающих немецкий язык через N, а множество студентов, изучающих английский – через А, множество всех студентов – через С.  Тогда n(N)=20,  n(A)=15, n(С)=50.

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

а)  n( NA)=0, n(NA)=n(N)+N(A)=20+15=35;

b)  n( NA)=?, n(NA)=?;

c)  n( NA)=n(A)=15, n(NA)=n(N)=20.

Таким образом, число студентов, изучающих оба языка (обозначим через х):  0  х  15, а число студентов, изучающих хотя бы один из языков (обозначим через y):   20  y  35.

Задача 3. В классе 30 человек. Из них 26 человек занимается баскетболом, 25 – плаванием, 27 – лыжами, 15 занимаются баскетболом и плаванием, 18 – плаванием и лыжами, 16 посещают секции по баскетболу и лыжам. Один ученик освобожден от физкультурных занятий. Сколько человек занимается всеми указанными видами спорта? Сколько человек занимается только одним видом спорта?

Решение: В задаче рассматриваются три множества: множество А – учащихся, играющих в баскетбол, множество В – занимающихся плаванием и множество С – посещающих лыжную секцию. По условию эти множества попарно пересекаются и в объединении дают 40-1=39.

Обозначим  n(ABC)= x. Определим  число  учащихся в каждой непересекающейся области  (рис. 44). Так как n(A)=26,  n(B)=25,  n(C)=27, n(AB)=15, n(BC)=18, n(AC)=16, то число детей, посещающих только баскетбол и плавание, равно (15-х), только плавание и лыжи – (18-х), баскетбол и плавание – (16-х), только баскетболом занимаются 26-(15-х)-(16-х)-х=х-5
детей, только плавание посещает 25-(15-х)-(18-х)-х=х-8  человек и, наконец, только лыжами – 27-(16-х)-(18-х)-х=х-7 учащихся.                                                                                

Задача 4. Пусть число дождливых дней равно 12, ветреных – 8, холодных – 4, дождливых и ветреных – 5, дождливых и холодных – 3, ветреных и холодных – 2 . Наконец, дождливых, ветреных и холодных – 1.

Тогда общее число плохих дней можно вычислить так: n(AAA)=n(A)+n(A)+n(A)-n(AA)-n(AA)-n(AA)-n(AAA)=12+8+4-5-3-2+1=15.

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

Решение: Цифры в записи числа могут повторяться и не повторяться. Рассмотрим первый случай. Тогда первую цифру в записи числа можно выбрать тремя способами (это может быть любая из данных цифр), вторую – также тремя и третью – тремя способами. Используя правило произведения, получаем: 333=27 чисел. Во втором случае – первую цифру можно выбрать тремя способами, вторую двумя (так как цифры не должны повторяться) и третью – одним способом. В этом случае таких чисел будет равно 321=6.

Задача 6. Из деревни А в деревню В ведут три дороги, а из В в С ведут две дороги. Сколькими способами можно пройти из А в С через В?

Чтобы решить данную задачу, обозначим дороги из А в В числами 1,2,3, а из В в С – буквами a, b. Тогда каждый вариант пути из А в С задается парой, состоящей из числа и буквы. Например, (2; a). Но число пар такого вида по правилу произведения равно 3 2 = 6. Вот эти варианты: (1;a), (2;a),(3;a), (1;b), (2;b), (3;b).