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

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

Definition

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

Scope

Данная тема представляет формулу включения-исключения и ее применение для подсчета объектов, которые избегают списка запрещенных свойств: беспорядки, сюръекции, функция Эйлера и количество целых чисел, взаимно простых с данным числом. В ней вводится понятие «решета» и обобщение функции Мёбиуса на частично упорядоченных множествах, что помещает принцип в более широкий алгебраический контекст.

Core questions

• Сколько элементов удовлетворяют хотя бы одному из нескольких перекрывающихся условий?
• Как можно подсчитать объекты, избегающие всех запрещенных свойств из заданного набора?
• Как из принципа следуют подсчеты беспорядков и сюръекций?
• Как функция Мёбиуса на частично упорядоченном множестве обобщает принцип включения-исключения?

Key concepts

• Объединение перекрывающихся множеств
• Метод решета
• Беспорядки через включение-исключение
• Подсчет сюръекций
• Функция Эйлера
• Функция Мёбиуса на частично упорядоченных множествах

Key theories

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

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

Обращение Мёбиуса на частично упорядоченных множествах

Обобщение Стэнли на частично упорядоченных множествах заменяет знакопеременные знаки включения-исключения функцией Мёбиуса частично упорядоченного множества, объединяя принцип с теоретико-числовыми и решеточно-теоретическими формулами обращения.

Clinical relevance

Идея «решета» обобщается на теорию чисел (решето Эратосфена и аналитические решета), теорию вероятностей (неравенства Бонферрони, ограничивающие вероятности объединений) и анализ надежности систем с перекрывающимися режимами отказа.

History

По существу сформулированный де Муавром и Сильвестром, принцип был помещен в общую теорию функций Мёбиуса на частично упорядоченных множествах Ротой в 1964 году, что стало важной вехой в современной комбинаторике.

Key figures

• Abraham de Moivre
• Gian-Carlo Rota

Seminal works

• stanley2011

Frequently asked questions

Почему знаки чередуются?

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

Какова связь с функцией Мёбиуса?

Включение-исключение является частным случаем обращения Мёбиуса на булевой решетке подмножеств, где функция Мёбиуса принимает значения плюс или минус один.