01. Формула включения и исключения

Основной задачей комбинаторики как раздела дискретной математики является определение числа элементов конечного множества, обладающих заданным набором свойств.

Теорема.1.1. (Формула включения и исключения).

Пусть даны конечных множеств , содержащих соответственно элементов. Тогда

Для решения комбинаторных задач используются частные случаи формулы включения и исключения.

Теорема.1.2. Для любых двух конечных множеств .

Пример. 9 студентов группы посещают лыжную и баскетбольную секции; 12 человек – баскетбольную и волейбольную, причём в баскетбольную секцию ходят 4 человека из группы. Сколько студентов данной группы занимаются спортом?

Решение. Обозначим символом множество студентов, посещающих лыжную и баскетбольную секции, по условию задачи . Обозначим символом множество студентов, посещающих баскетбольную и волейбольную секции, по условию задачи . Тогда множество есть множество студентов, посещающих баскетбольную секцию, множество есть множество студентов, занимающихся спортом. По условию задачи . Для ответа на вопрос задачи надо вычислить . По теореме 1.2. .□

Теорема 1.3. Для любых трёх конечных множеств

.

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

Используются теорема 1.2, свойства ассоциативности объединения множеств, дистрибутивности объединения и пересечения множеств.

■

Пример. В группе второго курса 13 студентов. Каждый из них участвовал хотя бы в одной университетской олимпиаде. Десять студентов принимали участие в олимпиаде по математике, семеро – в олимпиаде по физике и шестеро – в олимпиаде по информатике. Пятеро студентов участвовали в олимпиадах по математике и физике, четверо – в олимпиадах по математике и информатике, трое –в олимпиадах по физике и информатике. Найдите число студентов, участвовавших во всех трех олимпиадах.

Решение. Введем обозначения: - множество студентов, принимавших участие в олимпиаде по математике; - множество студентов, принимавших участие в олимпиаде по физике, - множество студентов, принимавших участие в олимпиаде по информатике. По условию задачи , , . Тогда множество есть множество студентов, участвовавших в олимпиадах по математике и физике, множество есть множество студентов, участвовавших в олимпиадах по математике и информатике, множество есть множество студентов, участвовавших в олимпиадах по физике и информатике. По условию задачи , , . Множество есть множество студентов, участвовавших хотя бы в одной олимпиаде. Множество есть множество студентов, участвовавших во всех трёх олимпиадах. По условию задачи . Для ответа на вопрос задачи надо найти . По теореме 1.3

.□

Задачи и упражнения.

1.1. Среди студентов первого курса университета 30 человек посещают факультативные занятия по физике и математике. Известно, что углублённо изучают оба предмета 10 студентов, математику – 25 человек. Сколько студентов посещают факультативные занятия по физике?

1.2. В отчёте о языковой подготовке студентов первого курса сказано, что из 100 первокурсников английский язык в школе изучали 50 человек, немецкий – 23, французский – 30. С английским и французским языками знакомы 8 студентов, с французским и немецким – 10, с английским и немецким – 20. Все три языка изучали 5 первокурсников. Докажите, что в отчёте есть ошибка. Исправьте ошибку, если известно, что при обработке данных произошла потеря информации.

1.3. Каждый студент группы занимается или спортом, или музыкой, или рисованием. Известно, что 23 студента увлечены спортом, 12 занимаются музыкой, 9 – занимаются рисованием. Семеро студентов совмещают занятия музыкой и увлечение спортом, трое студентов – занятия музыкой и рисованием, двое студентов – увлечение спортом и занятие рисованием. Один студент увлечен спортом, занимается музыкой и рисованием. Найдите число студентов в группе.

1.4. Из 30 студентов, участвовавших в экскурсионной поездке, все, кроме одного, рассказали сокурсникам о своих впечатлениях. О посещении музея с восторгом вспоминали 12 человек, о театральном спектакле - 10 человек, о джазовом концерте -13 человек. Пятеро студентов запомнили посещение музея и театра, трое студентов - посещение музея и концерта, четверо студентов - посещение театра и концерта. Шестеро студентов рассказали о посещении одновременно музея, театра и концерта. Сколько студентов участвовали в экскурсионной поездке?

Следующая >