Дискретная математика

Правило суммы: Пусть А и В – конечные множества. Тогда: |А ∪ В | = |А| + |В| − |А∩В|

Доказательство. Очевидно, что А∪В = А∪(В\А) и А∩(В\А) = ∅. Тогда

|А∪В| = |А|+|В\А| по предыдущей теореме. Аналогично, |В| = |В\А|+

|В∩А|. Следовательно |В\А| = |В|−|В∩А| и |А∪В | = |А|+|В|−|А∩В |. Теорема доказана.

В группе 25 студентов. Из них 16 учат английский язык, 14 учат немецкий язык. Сколько студентов изучают оба языка?

Решение: Будем считать что каждый студент изучает хоть один язык, то 16+14=30; 30-25 = 5 студентов изучают оба языка.

Замок открывается при правильном наборе двух букв и двух цифр. Сколько имеется таких комбинаций?

Решение: М^н= (33+10)⁴=43⁴ = 34118801 вариантов комбинаций.

Из города «А» в город «В» ведут 3 дороги, а из города «В» в город «С» ведут 5 дорог. Сколько дорог ведут из города «А» в «С».

Решение: 3*5=15 различных способов приехать из «А» в «С».

Предыдущая задача в случае когда имеет ещё 4 дороги из «А» в «С», минуя город «В»

Решение: 15+4=19

Рассылка 7 писем 4 курьерами. Сколько способов рассылки?

Решение: 4⁷= 16384

Разгрузка лифта в котором 5 человек, идущем с первого этажа на восьмой этаж.

Решение: Обозначим через X множество пассажиров, через Y – множе-

ство этажей, на которых они могут выйти. Тогда каждая разгрузка лифта –

это некоторое отображение f : X → Y (каждому пассажиру поставлен в со-

ответствие этаж, на котором он выходит при этой разгрузке). Следовательно

число различных способов разгрузки лифта совпадает с числом различных

отображений из множества X в множество Y , то есть равно |X^Y|= 8⁵ = 32768