Коррекция пересчета
В комбинаторике часто приходится считать элементы перекрывающихся множеств. Если просто сложить размеры множеств, пересечения будут посчитаны несколько раз. Принцип включений-исключений дает систематический способ исправить это. Для двух множеств формула проста:
|A ∪ B| = |A| + |B| - |A ∩ B|
Для трех множеств мы вычитаем попарные пересечения, но затем должны добавить обратно пересечение всех трех, так как оно было вычтено лишний раз. Этот паттерн чередования знаков продолжается для любого количества множеств.
Принцип Дирихле (Pigeonhole Principle)
Формулировка проста: если у вас есть n предметов (голубей) и m ящиков, причем n > m, то хотя бы в одном ящике окажется более одного предмета.
Пример: В городе с населением 1 миллион человек, если ни у кого нет более 500,000 волос на голове, мы гарантируем (с вероятностью 100%), что найдутся как минимум два человека с абсолютно одинаковым числом волос. Нам не нужно их искать или считать — логика делает этот факт неизбежным.
Связанные темы
Эта тема тесно связана с Комбинаторными парадоксами, где логика бросает вызов интуиции.
