А можно ли,с учетом ошибок,для грубого доказательства формулы включений\исключений использовать следующее:
Дана формула включений\исключений:
Введем комбинаторную интерпретацию:
Пусть есть n множеств
Тогда:
Выбрать одинарные множества из n множеств есть
способов
Выбрать двойные множества из n множеств есть
способов
Выбрать тройные множество из n множеств есть
способов
Выбрать n-ые множества из n множеств есть
способов
Тогда по формуле включений\иключений получается:
Далее нужно получить формулу
и доказать что
Получить формулу
и доказать что
можно из формулы знакопеременной разности биноминальных коэффициентов
Для этого возьмем саму формулу знакопеременной разности биноминальных коэффициентов:
Обозначим
Тогда формула принимает вид:
Далее перенесем
в правую часть равенства и получим:
или же
Как итог мы получили формулу
и доказали что
Формула
в точности равна правой части формулы включений\исключений
А как было доказано раннее
Значит в правой части формулы включений\исключений каждый элемент учитывается ровно 1 раз.
В левой части формулы включений\исключений каждый элемент так же учитывается ровно 1 раз(так как это объединение)
Следовательно левая и правая часть формулы включений\исключений равны.
Формула включений\исключений доказана