Математика 9 класс 9-М-7

§5. Формула включений и исключений

Формулу включений и исключений для множеств вы проходили в предыдущем задании («Элементы теории множеств. Элементы логики»), и выглядела для двух множеств она так:

mAB=mA+mB-mABm\left( A \bigcup B \right) = m\left( A \right) + m\left( B \right) - m\left( A \cap B \right),

где AA, BB – множества, а mm – количества элементов в множествах.

Напомним, правило суммы требует, чтобы все способы выбора какого-то объекта фактически были разделены на два множества, A1A_1 и A2A_2, причем «объект a1a_1 можно выбрать n1n_1 способами», что означает, что mA1=n1m\left(A_1\right) = n_1, «объект a2a_2 можно выбрать n2n_2 способами». Фраза «результаты выбора объектов a1a_1 и a2a_2 никогда не совпадают» означает, что A1A2=A_1 \cap A_2 = \varnothing, а фраза «выбор «либо a1a_1, либо a2a_2» можно осуществить n1+n2n_1 + n_2 способами» означает, что mA1A2=n1+n2m\left(A_1 \bigcup A_2\right) = n_1 + n_2. Таким образом, правило суммы говорит, что

mA1A2=mA1+mA2m\left( A_1 \bigcup A_2 \right) = m\left( A_1 \right) + m\left( A_2 \right),

если A1A2=A_1 \cap A_2 = \varnothing – правило суммы является частным случаем формулы включений и исключений.

Формулу включений можно применять при подсчёте количества способов, когда правило суммы применить не получается – не получается разбить множество способов выбора на непересекающиеся множества. Можно не выписывать каждый раз эту формулу. Главное – запомните, если вы считаете количество способов, то каждый способ должен быть посчитан ровно один раз. Если ваш подсчёт подразумевает, что этот способ был подсчитан более одного раза, то нужно выделить лишнее, затем выделенное отнять отдельно

Пример 16

(Физтех-2012) Дан правильный 14-угольник. Найдите количество четвёрок его вершин, являющихся вершинами выпуклых четырёхугольников, в которых хотя бы один угол равен `90^@`. (Две четвёрки вершин, отличающиеся порядком вершин, считаются одинаковыми.)


Решение

Впишем наш правильный 14-угольник X1X2X3X14X_1X_2X_3 \: … \: X_{14} в окружность. Тогда по свойству вписанных углов прямой угол должен опираться на диаметр. Таким образом, нас интересуют четверки вершин такие, что две точки лежат на диаметре, а две остальные – по разные стороны этого диаметра. Диаметров – семь (X1X8,X2X9,,X7X14X_1X_8,\: X_2X_9 , \:… \: , X_7X_{14}), точек по каждую сторону – по шесть. По правилу произведения получим, 7×6×6=2527 \times 6 \times 6 = 252 варианта. Но при таком подсчёте прямоугольники (т. е. четырёхугольники, у которых обе диагонали являются диаметрами) посчитаны дважды. Прямоугольников выходит C72=21C_7^2 = 21 штука, и в итоге получаем 25221=231252 − 21 = 231 способ.

ОТВЕТ

`231` четвёрка

Заметим, что в данном решении мы формально не применяли формулу включений и исключений, но вычли посчитанные дважды варианты. Приведем решение, в котором формула включений и исключений будет видна явно. Для этого придется упорядочить наш четырехугольник: две четвёрки вершин, отличающиеся порядком вершин, теперь
будем считать «разными». Одной «одинаковой» четверке вершин, взятых по часовой стрелке, Y1Y2Y3Y4Y_1Y_2Y_3Y_4 сдвигами соответствуют четыре «разных» - Y2Y3Y4Y1Y_2Y_3Y_4Y_1, Y3Y4Y1Y2Y_3Y_4Y_1Y_2, Y4Y1Y2Y3Y_4Y_1Y_2Y_3 и исходный Y1Y2Y3Y4Y_1Y_2Y_3Y_4. Таким образом, полученный ответ нужно будет поделить на 4.

Пусть AA – множество четырёхугольников, у которых Y1Y3Y_1Y_3 – диаметр. Количество способов выбрать точку Y1Y_1 – 14. После выбора Y1Y_1 одним способом выбираем Y3Y_3 (диаметрально противоположная), затем по шесть способов Y2Y_2 и Y4Y_4, итоговое количество способов по правилу произведения равно 14×6×6=50414 \times 6 \times 6 = 504.

Пусть BB – множество четырёхугольников, у которых Y2Y4Y_2Y_4 – диаметр, их также 504. Нас интересует количество четвёрок точек с хотя бы одним диаметром, т. е. mABm\left(A \bigcup B\right). Формула включений и исключений выдает ответ: mAB=504+504mABm\left(A \bigcup B\right) = 504 + 504 − m\left(A \cap B\right) . Осталось найти mABm\left(A \cap B\right) – т. е. количество прямоугольников. Вершину Y1Y_1 такого прямоугольника можно выбрать четырнадцатью способами. После выбора Y1Y_1 выбор диаметральной противоположной Y3Y_3 – одним способом. Поскольку мы условились, что вершины Y1Y2Y3Y4Y_1Y_2Y_3Y_4 следуют по часовой стрелке, выбор Y2Y_2 можно осуществить шестью способами, и, наконец, выбор Y4Y_4 – одним. Общее количество прямоугольников равняется 14×1×6×1=8414 \times 1 \times 6 \times 1 = 84, а ответ - 504+50484=924504 + 504 − 84 = 924. Это ровно в четыре раза больше уже полученного ответа `231`, ч. т. д.
Таким образом, решение со строгим применением формулы включений и исключений получилось сложнее решения, в котором варианты, посчитанные дважды, были отняты.

Формула включений и исключений более интересна в случае нескольких множеств и выглядит для трёх множеств она так:

$$m\left( A \cup B  \cup C \right) = m\left( A \right) + m\left( B \right)  + m\left( C \right)  - m\left( A \cap B \right) - m\left( A \cap C \right) -$$

$$- m\left( C \cap B \right) + m\left( A \cap B  \cap C \right)$$.

В случае четырёх и более множеств, чтобы найти количество элементов в объединении - нужно сложить количества элементов в множествах, отнять количества элементов во всех попарных пересечениях, прибавить количества элементов во всех пересечениях по три, снова отнять количества элементов во всех пересечениях по четыре и т. д., чередуя знаки, до пересечения всех множеств, количество элементов которых необходимо либо отнять, либо прибавить в зависимости от чётности количества множеств изначально.