PPt4Web Хостинг презентаций

Главная / Математика / Формула включений-исключений. Беспорядки
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

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


Скачать эту презентацию

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


Скачать эту презентацию



№ слайда 1 § 4. Формула включений-исключений. Беспорядки. § 4. Формула включений-исключений
Описание слайда:

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

№ слайда 2 Доказательство. Возьмем элемент а А. Доказательство. Возьмем элемент а А. В числ
Описание слайда:

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

№ слайда 3 единиц, так как a входит во все пересечения единиц, так как a входит во все пере
Описание слайда:

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

№ слайда 4 Чтобы доказать теорему, осталось доказать равенство Но это равенство равносильно
Описание слайда:

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

№ слайда 5 которое верно, так как является следствием бинома Ньютона при х = -1. которое ве
Описание слайда:

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

№ слайда 6 Наиболее часто формулу включений-исключений применяют в несколько иной формулиро
Описание слайда:

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

№ слайда 7 Теорема 2. Теорема 2.
Описание слайда:

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

№ слайда 8 Пример. Вычислить количество натуральных чисел, не превосходящих 100, которые не
Описание слайда:

Пример. Вычислить количество натуральных чисел, не превосходящих 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.

№ слайда 9 Определение 3. Пусть дано множество Определение 3. Пусть дано множество А = {1,
Описание слайда:

Определение 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).

№ слайда 10 Теорема 4. Число беспорядков n-элементного множества равно Теорема 4. Число бесп
Описание слайда:

Теорема 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)!

№ слайда 11 Пусть N(i1, i2, …, ik ) – количество перестановок, в которых числа i1, i2, …, ik
Описание слайда:

Пусть 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 – количество беспорядков множества А, по формуле включений – исключений получаем:

№ слайда 12
Описание слайда:

№ слайда 13 Пример. Вернемся к предыдущему примеру. Непосредственным подсчетом мы выясним, ч
Описание слайда:

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

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru