Презентация на тему: Формула включений-исключений. Беспорядки

§ 4. Формула включений-исключений. Беспорядки. § 4. Формула включений-исключений. Беспорядки. Теорема 1 (формула включений-исключений). Пусть А = А1 А2 … Аm – конечное множество. Тогда

Доказательство. Возьмем элемент а А. Доказательство. Возьмем элемент а А. В число, стоящее слева, этот элемент «вносит» единицу. Подсчитаем, какое число соответствует элементу в правой части доказываемого равенства. Если мы докажем, что оно также равно 1, то теорема будет доказана. Пусть a входит в k множеств Тогда в первое слагаемое элемент a «вносит» k единиц, во второе слагаемое элемент а «вносит»

единиц, так как a входит во все пересечения единиц, так как a входит во все пересечения такие, что и содержат a; число таких пересечений – число 2-х элементных подмножеств k-элементного множества, т.е. В l-ое слагаемое a «вносит» единиц (l k). Если l > k, то a в такие пересечения уже не входит, те есть «вносит» в эти суммы 0. Таким образом a «вносит» в правую сумму следующее количество единиц:

Чтобы доказать теорему, осталось доказать равенство Но это равенство равносильно следующему :

которое верно, так как является следствием бинома Ньютона при х = -1. которое верно, так как является следствием бинома Ньютона при х = -1. Теорема доказана.

Наиболее часто формулу включений-исключений применяют в несколько иной формулировке. Наиболее часто формулу включений-исключений применяют в несколько иной формулировке. Пусть имеется N предметов, каждый из которых может обладать или не обладать одним из свойств Р1, Р2, …, Рm. Введем следующие обозначения: N(Pi) – количество предметов, которые обладают свойством Pi, - количество предметов, которые не обладают свойством Pi, причем не важно, обладают они или нет другими свойствами, - количество предметов, которые обладают свойствами и не обладают свойствами , и т. п.

Теорема 2. Теорема 2.

Пример. Вычислить количество натуральных чисел, не превосходящих 100, которые не делятся на 2, 3, 5. Пример. Вычислить количество натуральных чисел, не превосходящих 100, которые не делятся на 2, 3, 5. Решение. N = 100. Обозначим через N(2) количество чисел из N, которые делятся на 2 и далее аналогично. Тогда N(2) = 50, N(3) = 33, N(5) = 20, N(2,5) = N(10) = 10, N(2,3) = N(6) = 16, N(3,5) = N(15) = 6, N(2,3,5) = N(30) = 3. По формуле включений-исключений получаем: N= 100 – N(2) – N(3) – N(5) + N(2,3) + N(3,5) + N(2,5) – N(2,3,5) = 100 – 50 – 33 – 20 + 16 + 10 + 6 – 3 = 32.

Определение 3. Пусть дано множество Определение 3. Пусть дано множество А = {1, 2, 3, …, n}. Перестановка (к1, к2,…, кn) называется беспорядком, если кi ≠ i для любого i n, то есть каждое число не стоит на своем месте. Пример. Пусть А = {1, 2, 3, 4}. Выпишем все беспорядки: (2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,1,2), (4,3,2,1).

Теорема 4. Число беспорядков n-элементного множества равно Теорема 4. Число беспорядков n-элементного множества равно Доказательство. Введем обозначения: N(i) – количество перестановок, у которых на i-м месте стоит число i. Поскольку все остальные (n-1) числа могут стоять произвольно, то N(i) = (n-1)! (i = 1, 2, 3, …, n). Пусть N(i, j) – количество перестановок, в которых числа i и j стоят на i-м и j-м местах соответственно, N(i, j) = (n – 2)!

Пусть N(i1, i2, …, ik ) – количество перестановок, в которых числа i1, i2, …, ik стоят на местах с этими же номерами соответственно, Пусть N(i1, i2, …, ik ) – количество перестановок, в которых числа i1, i2, …, ik стоят на местах с этими же номерами соответственно, N(i1, i2, …, ik ) = (n – k)!. Отметим так же, что количество чисел вида N(i1, i2, …, ik ) существует столько же, сколько существует k-элементных подмножеств n-элементного множества, то есть . Обозначив через Dn – количество беспорядков множества А, по формуле включений – исключений получаем:

Пример. Вернемся к предыдущему примеру. Непосредственным подсчетом мы выясним, что число беспорядков D4 = 9. Вычислим D4, используя полученную формулу: Пример. Вернемся к предыдущему примеру. Непосредственным подсчетом мы выясним, что число беспорядков D4 = 9. Вычислим D4, используя полученную формулу: