2.4 Правило суммы

 

Теорема 1. Пусть А и В – конечные непересекающиеся множества (т. е. ), тогда

.                                    (1)

 

Теорема 2 (следствие предыдущей)  Пусть А, В – конечные множества, тогда

                         (2)

Теорема 3 (правило включения-исключения) Пусть  – конечные множества, тогда

  (3)

 

В правой части формулы (3), называемой формулой включения-исключения, стоят с чередующимися знаками скобки, содержащие всевозможные попарные пересечения множеств , пересечения троек множеств и т. д.

Теорема 4 (правило суммы) Если  – конечное попарно непересекающиеся множества (т. е. ), то

                                                    (4)

Ясно, что это тривиальное следствие из предыдущей теоремы.

Определение 1. Декартовым произведением множеств  и  называется множество, обозначаемое , элементами которого являются упорядоченные пары , где , . Равенство упорядоченных пар понимается в следующем смысле:

пусть   и , ,

.

Теорема 5. Если  и  – конечные множества, то  – конечное множество и

                                              (5)

Определение 2.  Пусть  – множество и . Определим декартовы степени множества  следующим:

;

;

…

.

Теорема 6. Если  – конечное множество, то

                                                  (6)

Ясно, что теорема 6 – следствие теоремы 5.

Задача 1. Из города А в город В ведет три дороги, а из города В в город С – 4 дороги. Сколькими  способами можно добраться из А в С через В?

* Под способом попасть из А в С через В понимать упорядоченную пару (дорога, по которой перемещаемся из А в В; дорога, по которой перемещаемся из В в С), то решение задачи можно получить, используя понятие декартова произведения. Обозначим:

АВ – множество дорог, ведущих из А в В;

ВС – множество дорог, ведущих из В в С.

Тогда математическая задача, к которой свелась исходная задача, выглядит так: «Найти число элементов в декартовом произведении АВВС».

     Ясно, что │ АВВС│=│АВ│•│ ВС│=3•4=12.

Ответ: 12 способов.

Задача 2. Из города А в город В ведет три дороги, а из города В в город С – 4 дороги; имеется также 5 дорог из А в С, не проходящих через В. Сколькими  способами можно добраться из А в С, используя указанные дороги?

*Множество всех способов добраться из А в С разобьем на непересекающиеся подмножества I и II, отнеся к первому способы добраться из А в С через В, а ко второму – способы добраться из А в С, минуя В. Тогда по правилу суммы «число способов попасть из А в С»=│ I│+│ II│= │АВВС│+│II│= 3•4+5=17.

Ответ: 17 способов.