Теоремы о сложении и умножении

Теорема о сложении:

Пусть объект может быть выбран способами, - и т.д. - , тогда выбор одного из объектов , , может быть осуществлено + + (= ) способами.

Теорема об умножении:

Пусть элемент может быть выбран способами, - и т.д. - , тогда выбор , , (упорядоченный) может быть осуществлен * *

Доказательство:

K=2

1,2… - способы выбора элемента

Каждому из них соответствует способов выбрать элемент

(1,Х) - пар

(2,Х) - пар

…

(, Х) - пар

Общее число ={ } =

К=3

1,2… - способы выбора

Каждому из них соответствует * способов выбора двух других элементов

(1, Х, У) - *

(2, Х, У) - *

…

(, Х, У) - *

* + * +…+ * = *

2) Формула включений – исключений.

Теорема: пусть имеется K свойств (1, 2, …, К), несколько объектов, каждый из которых может удовлетворять или не удовлетворять свойствам. – количество объектов, удовлетворяющие всем свойствам . , тогда количество объектов (Х), удовлетворяющих хотя бы одному из этих свойств, может быть посчитано:

Х = (

K – нечетное => последнее слагаемое с «+»

Следствие:

Если К=2, то

Х=

Если К = 3, то

Х=

Доказательство:

Теорема о сложении:

К=2

Х= , где

У – число элементов, удовлетворяющих и не удовлетворяющих , т.е. У+ = =>

Х= +( - )= + -

Теорема об умножении:

К=3

Х= +( + - )-( + + )= + + - -( + + )

Пусть У – число элементов, удовлетворяющих и хотя бы одному или ,

Z – количество элементов, которые удовлетворяют хотя бы одному или