Теорема II

Следствие.

Теорема I.

Пример 2.

Основные законы комбинаторики. Правило суммы.

Если на блюде лежат 7 яблока и 4 груши, то выбрать один плод можно 7+4=11 способами. В общем виде: если элемент a можно выбрать m способами, а элемент b n способами, причем любой выбор элемента a будет отличен от выбора элемента b, то выбор a или b можно сделать m + n способами. На языке теории множеств это правило формулируется следующим образом.

Если пересечение конечных множеств A и B пусто , то число элементов в их объединении равно сумме чисел элементов множеств A и B:

. (1)

Если конечные множества попарно не пересекаются, то есть если при , то справедливо равенство

. (2)

Рассмотрим случай, когда множества могут иметь не пустые пересечения.

Для любых конечных множеств A и B верно равенство

. (3)

Формула (3) является частным случаем более общей формулы

, (4)

которую называют формулой включений и исключений. При m = 3 имеем число элементов

. (5)

Дата добавления: 2015-06-26