§ 4. Формула включений-исключений. Беспорядки. § 4. Формула включений-исключений. Беспорядки. Теорема 1 (формула включений-исключений). Пусть А = А1 А2…Аm – конечное множество. Тогда
Содержание
- 2. Доказательство. Возьмем элемент а А. В число, стоящее слева, этот элемент «вносит» единицу. Подсчитаем, какое число
- 3. единиц, так как a входит во все пересечения такие, что и содержат a; число таких пересечений
- 4. Чтобы доказать теорему, осталось доказать равенство Но это равенство равносильно следующему :
- 5. которое верно, так как является следствием бинома Ньютона при х = -1. Теорема доказана.
- 6. Наиболее часто формулу включений-исключений применяют в несколько иной формулировке. Пусть имеется N предметов, каждый из которых
- 7. Теорема 2.
- 8. Пример. Вычислить количество натуральных чисел, не превосходящих 100, которые не делятся на 2, 3, 5. Решение.
- 9. Определение 3. Пусть дано множество А = {1, 2, 3, …, n}. Перестановка (к1, к2,…, кn)
- 10. Теорема 4. Число беспорядков n-элементного множества равно Доказательство. Введем обозначения: N(i) – количество перестановок, у которых
- 11. Пусть N(i1, i2, …, ik ) – количество перестановок, в которых числа i1, i2, …, ik
- 14. Скачать презентацию