Формула включений-исключений: Искусство точного подсчета
Когда нам нужно подсчитать количество объектов, обладающих определенными свойствами, мы часто сталкиваемся с проблемой пересечений. Если в классе из 30 человек 20 изучают английский язык, а 15 — немецкий, мы не можем просто сложить 20 и 15 (получится 35, что больше числа учеников). Некоторые ученики изучают оба языка, и при простом сложении мы посчитали их дважды. Для решения таких задач в комбинаторике используется мощнейший инструмент — формула включений-исключений.
Логика метода отражена в его названии. Чтобы найти мощность объединения нескольких множеств, мы сначала включаем (суммируем) мощности каждого множества по отдельности. Затем мы исключаем (вычитаем) мощности попарных пересечений этих множеств (так как они были посчитаны дважды). Однако при этом мы случайно вычли элементы, принадлежащие одновременно трем множествам, поэтому их пересечения нужно снова включить (прибавить). Этот процесс альтернирующего (чередующегося) знака продолжается до тех пор, пока не будет учтено пересечение всех имеющихся множеств.
Одно из самых знаменитых применений этой формулы — Задача о беспорядках (Derangements), известная также как задача о проверке шляп. Если N джентльменов сдают в гардероб N шляп, а рассеянный гардеробщик выдает им шляпы абсолютно случайным образом, какова вероятность того, что ни один человек не получит свою собственную шляпу? Применяя метод включений-исключений к перестановкам без неподвижных точек (субфакториалам), дискретная математика дает поразительный ответ: при стремлении N к бесконечности эта вероятность стремится к 1/e (примерно 36.8%).
В информатике принцип включений-исключений активно применяется в теории вероятностей, алгоритмах на графах и теории чисел. С его помощью выводится Функция Эйлера (φ(n)), подсчитывающая количество чисел, взаимно простых с заданным числом n (что критически важно для генерации ключей в криптосистеме RSA). В базах данных этот принцип используется оптимизаторами SQL-запросов для быстрой оценки количества строк, которые вернутся при выполнении сложных условий фильтрации с множественными операторами OR, помогая СУБД выбрать оптимальный план выполнения запроса.
