Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Принцип включения и исключения Комбинаторика

eyJpZCI6ImE1MjA1MTM2ZjAxZDIyNDY1ZTc5ZmJlMTgzZmJmYTMxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=2cafe3af0102e3368a76c53a938bf413276be3cbbb387cbe3103b7601ab78a35

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

Задача усложнится, если нужно найти число людей с большим количеством свойств. Допустим, нас интересует не только английский язык, но и еще пять других. В таком случае придется выполнить много вычислений. В математике для этого применяют принцип включения и исключения.

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

Принцип включения и исключения

Этот принцип применяется, когда нужно вычислить количество элементов, у которых есть хотя бы одно из нескольких свойств. При этом элементы, у которых есть более чем одно свойство, не учитываются дважды. Здесь происходит сложение и вычитание количества элементов, которые подходят хотя бы одной из двух категорий — поэтому двойной подсчет делать не нужно.

Представим, что нам нужно найти число людей, у которых есть хотя бы одна кошка или собака. Мы знаем, что у пяти человек есть кошка, а у восьми — собака. Также у трех из них есть и кошка, и собака.

Получается следующее решение:

— число людей, у которых есть хотя бы одна кошка или одна собака

PIE полезен в комбинаторике и теории вероятности, так как гарантирует, что объект не посчитается дважды.

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

Как это работает на практике

Представим, что нам снова нужно найти людей, у которых есть хотя бы одна кошка или собака. Но теперь у нас есть две рассматриваемые группы — два множества.

Когда объекты разделяются на два множества, принцип включения и исключения гласит:

В этом случае обозначает кардинальность или мощность — то есть количество элементов множества в нотации множеств.

Докажем это утверждение.

Как доказать принцип включения и исключения

Для начала нужно показать, как учитывать элементы:

  • Если элемент входит в одно из двух множеств, он учитывается один раз

  • Если элемент не входит в эти множества, он учитывается ноль раз

Рассмотрим четыре случая:

  1. Элемента нет ни в , ни в

  2. Элемент находится в , но не в

  3. Элемент находится в , но не в

  4. Элемент находится в и в

Вот так PIE для двух множеств выглядит в виде диаграммы Венна:

eyJpZCI6IjI5N2FjNjAzNDQyMTljMjUzNGFhZDU5NTdkNjkwNGE2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=418d64c5b331a85afceb3a9fc248f5810356ff2c8434c8b4dd0aa1248124fee5

Рассмотрим доказательство на примере. Допустим, нам нужно узнать ответ на вопрос:

Сколько целых чисел от до кратны или ?

Далее зададим такие условия:

  • Пусть — множество целых чисел от до , кратных , тогда

  • Пусть — множество целых чисел от до , кратных , тогда

Затем найдем элементы, которые входят в оба множества:

  • — это множество целых чисел от до , которые кратны и

  • Делаем вывод, что целые числа из множества кратны

  • Следовательно, — количество элементов, которые кратны и

  • Далее перечислим эти 16 чисел:

В итоге мы получаем такую формулировку по PIE:

чисел от до кратны или

Выводы

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

PIE помогает из множества объектов выбрать те, которые обладают определенным свойством. При этом, он не учитывает их дважды. Поэтому решать такие задачи с помощью принципа включения и исключения проще и безопаснее.


Самостоятельная работа

Задача №1

Представим группу учеников, которая сдала выпускные экзамены:

  • учеников сдали английский язык

  • — сдали математику

  • — успешно сдали оба предмета

  • учеников завалили два экзамена

Найдите общее число выпускников.

Нажмите, чтобы увидеть ответ

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

Из условия:

  • успешно сдали оба предмета

Из этого следует, что:

  • сдали английский, но завалили математику

  • сдали математику, но завалили английский

Далее посчитаем, сколько учеников сдали хотя бы один экзамен. Для этого нужно сложить процент учеников, которые сдали оба экзамена или только математику или только английский:

  • сдали хотя бы один экзамен

Делаем такой вывод:

  • завалили два экзамена

  • В условии сказано, что это учеников

  • Значит, от общего числа кандидатов — это учеников

Делаем последний шаг:

  • выпускников сдавали экзамены



Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

Задавайте вопросы, если хотите обсудить теорию или упражнения. Команда поддержки Хекслета и опытные участники сообщества помогут найти ответы и решить задачу