Комбинаторный принцип сложения для пересекающихся множеств.
До настоящего момента непересекающиеся множества рассматривались только в связи с комбинаторным принципом сложения. Предположим, что множества S и Т не являются непересекающимися и требуется найти |S T|. Когда количество элементов множества S суммируется с количеством элементов множества Т, элементы, принадлежащие S T, учитываются дважды. Поэтому количество элементов, принадлежащих множеству S T, нужно из суммы вычесть. Отсюда получаем следующую теорему.
ТЕОРЕМА 8.12. Пусть S и Т - множества. Количество элементов, которое можно выбрать из S или Т, равно |S| + |Т| - | S T |. Иными словами, |S T| = |S| + |T| – |S T |.
ДОКАЗАТЕЛЬСТВО. Множество S T = (S – Т) (Т – S) (S T), где S – T, Т – S и S Т- попарно непересекающиеся множества. Поэтому | S T | = |S – T| + |T – S| + | S T |. Имеем также, что S = (S–T) (S T ) и T= (T–S) (S T), откуда |S| = |S – T| + | S T | и |T| = |T – S| + | S T |. Следовательно, |S| + |T| – | S T | = |S – T| + |T-S| + 2| S T| – |S T | = |S – T| + |T – S| + |S T | = |S T|.
ПРИМЕР 8.13. Предположим, что в группе из 100 студентов 60 человек изучают математику, 75 – историю, а 45 человек – и то, и другое.
а) Сколько студентов изучают математику или историю?
б) Сколько студентов не изучают ни математику, ни историю?
а) Пусть универсум U - группа из 100 студентов, М - множество студентов, изучающих математику, H – множество студентов, изучающих историю. Тогда количество студентов, изучающих математику или историю, равно |M H| = |M| + |H| – |M H| = 60 + 75 – 45 = 90.
б) Количество студентов, не изучающих ни математику, ни историю, равно|М’ Н’|. Но М' H' = (M Н)’, поэтому |М' Н'| = |(М Н)'| =100 – 90 = 10.
6.Перестановка
Перестановка – это переупорядочение набора объектов, или функция, которая задает такое переупорядочение(т.е порядок, в котором они отобраны имеет большое значение.)
ТЕОРЕМА 8.20. Количество способов выбрать r объектов с учетом порядка из n объектов равно
(n)(n – 1)(n – 2)(n – 3) … (n – j + 1) … (n – r + 1) = n! / (n– r)!
ОПРЕДЕЛЕНИЕ 8.21. Пусть P(n,r)= n! / (n – r)!. Р(n,r) называется числом
перестановок (размещений) из n объектов по r.
Заметим, что если выбирать все n объектов и размещать их в определенном порядке, то r = n и, поскольку 0! = 1, имеем число перестановок
ПРИМЕР
8.22. Сколько
различных четырехзначных чисел можно
образовать из цифр 1, 2, 3, ..., 9, если все
цифры в каждом четырехзначном числе
различны? Для
формирования каждого четырехзначного
числа выбираем четыре цифры из девяти,
поэтому существует
таких
различных чисел.
Сочетания
число сочетаний означает число выборок, которые могут быть сделаны из n элементов по r элементов — это все r-элементные подмножества n-элементного множества, где различными подмножествами считаются те, которые имеют различный состав элементов, при этом порядок отбора не важен.
ТЕОРЕМА
8.28. Количество
способов выбора r
объектов
из n
объектов
без учета порядка
равно
.
ОПРЕДЕЛЕНИЕ
8.29. Для
0 <
r
<
n
положим
С(n,r)
называется
числом сочетаний
из n объектов по r.
ТЕОРЕМА 8.30. Для 0 < r < n имеем С(n, r) = С(n, n–r).
ДОКАЗАТЕЛЬСТВО.
Обратите внимание, что в случае сочетаний, как и в случае перестановок (размещений), при выборе r объектов каждый объект может быть выбран не более одного раза.
Если выбираются все n объектов без учета порядка, то r = n. Поскольку 0! = 1. имеем
поэтому существует только один способ выбрать n элементов: просто взять их все.
ПРИМЕР 8.35. Сколькими способами можно вытянуть 5 карт трефовой масти из стандартной колоды, содержащей 52 карты? В колоде имеется 13 треф, из которых выбираются 5, поэтому существует
С(13,5) |
= |
|
13! 5!8! |
= 1287 |
возможных 5-карточных раскладов пяти треф.