Rambler's Top100





6
n(A
1
A
2
,…,
A
k
) = n(A
1
) · n(A
2
) ·,…, ·n(A
k
).
Доказательство. Доказать самостоятельно индукцией по k, при-
меняя теорему 3.
Рассмотрим несколько задач на применение принципов сложения и
умножения.
Задача 1. Пусть A и B конечные множества, B A. Сколько эле-
ментов содержит множества A
\
B.
Решение. Докажем, что в случае, когда B A, n(A
\
B) =
= n(A) n(B). В самом деле, запишем очевидное теоретико-множест-
венное равенство (A
\
B) B = A, причем (A
\
B) B = .
Применим к множествам A
\
B и B принцип сложения.
n((A
\
B) B) = n(A
\
B) + n(B) или n(A) = n(A
\
B) + n(B)
Отсюда получаем требуемое равенство n(A
\
B) = n(A) n(B).
Задача 2. Пусть A и B конечные множества. Сколько элементов
содержит множество A B.
Решение. Принцип сложения здесь непосредственно применять
нельзя, так как нет условия непересекающихся множеств A и B. В об-
щем случае имеет место формула n(A B) = n(A) + n(B)
n(A B). Для доказательства этого представим множество A B в
следующем виде: A B=(A
\(
A B
)
) (B
\(
A B)) (A B).
Все три множества A
\(
A B
)
, B
\(
A B), A B попарно не
пересекаются, поэтому здесь уже можно применить принцип сложения:
n(A B) = n(A
\(
A B)) + (B
\(
A B)) + (A B). Так как
A B A и A B B, то n(A
\(
A B)) = n(A) - n
(
A B) и
n(B
\(
A B)) = n(B) - n
(
A B). Поэтому окончательно получаем
n(A B) = n(A) - n
(
A B) + n(B) - n
(
A B) + n
(
A B) =
=n(A) + n(B) - n
(
A В).
И в заключении рассмотрим задачу, которая не только демонстри-
рует совместное применение принципов сложения и умножения, но и
является иллюстрацией дальнейших идей и понятий комбинаторики.
Задача 3. Из цифр A={0,1,2,3,5,6,7} составить все четырех-
значные числа, не содержащие повторяющихся цифр и делящиеся на 3.
Решение. Воспользуемся признаком делимости на три: число де-
лится на три в том и только в том случае, когда сумма цифр этого числа
делится на три. Поэтому надо перебрать всевозможные четверки цифр,
сумма которых делится на три. Перечислим такие четверки:
A
1
= {0, 1, 2, 3}, A
2
= {0, 1, 2, 6}, A
3
= {0, 1, 3, 5},
A
4
= {0, 1, 5, 6}, A
5
= {0, 2, 3, 7}, A
6
= {0, 3, 5, 7},