Презентация 4. Формула включений-исключений. Беспорядки. 4. Формула включений-исключений. Беспорядки. Теорема 1 (формула включений-исключений). Пусть А А1 А2…Аm – конечное множество. Тогда онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему 4. Формула включений-исключений. Беспорядки. 4. Формула включений-исключений. Беспорядки. Теорема 1 (формула включений-исключений). Пусть А А1 А2…Аm – конечное множество. Тогда абсолютно бесплатно. Урок-презентация на эту тему содержит всего 13 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:13 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:261.50 kB
- Просмотров:74
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: § 4. Формула включений-исключений. Беспорядки.
§ 4. Формула включений-исключений. Беспорядки.
Теорема 1 (формула включений-исключений).
Пусть А = А1 А2…Аm – конечное множество. Тогда
№2 слайд
Содержание слайда: Доказательство. Возьмем элемент а А.
Доказательство. Возьмем элемент а А.
В число, стоящее слева, этот элемент «вносит» единицу.
Подсчитаем, какое число соответствует элементу в правой части доказываемого равенства. Если мы докажем, что оно также равно 1, то теорема будет доказана.
Пусть a входит в k множеств
Тогда в первое слагаемое элемент a «вносит» k единиц, во второе слагаемое
элемент а «вносит»
№3 слайд
Содержание слайда: единиц, так как a входит во все пересечения
единиц, так как a входит во все пересечения
такие, что и содержат a;
число таких пересечений – число 2-х элементных подмножеств k-элементного множества, т.е.
В l-ое слагаемое a «вносит» единиц (l k). Если l > k, то a в такие пересечения уже не входит, те есть «вносит» в эти суммы 0. Таким образом a «вносит» в правую сумму следующее количество единиц:
№4 слайд
Содержание слайда: Чтобы доказать теорему, осталось доказать равенство
Но это равенство равносильно следующему :
№5 слайд
Содержание слайда: которое верно, так как является следствием бинома Ньютона при х = -1.
которое верно, так как является следствием бинома Ньютона при х = -1.
Теорема доказана.
№6 слайд
Содержание слайда: Наиболее часто формулу включений-исключений применяют в несколько иной формулировке.
Наиболее часто формулу включений-исключений применяют в несколько иной формулировке.
Пусть имеется N предметов, каждый из которых может обладать или не обладать одним из свойств Р1, Р2, …, Рm.
Введем следующие обозначения:
N(Pi) – количество предметов, которые обладают свойством Pi,
- количество предметов, которые не обладают свойством Pi, причем не важно, обладают они или нет другими свойствами,
- количество предметов, которые обладают свойствами и не обладают свойствами , и т. п.
№7 слайд
Содержание слайда: Теорема 2.
Теорема 2.
№8 слайд
Содержание слайда: Пример. Вычислить количество натуральных чисел, не превосходящих 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, 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. Число беспорядков 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 ) = (n – k)!.
Отметим так же, что количество чисел вида N(i1, i2, …, ik )
существует столько же, сколько существует k-элементных подмножеств n-элементного множества, то есть .
Обозначив через Dn – количество беспорядков множества А, по формуле включений – исключений получаем:
№12 слайд
Содержание слайда:
№13 слайд
Содержание слайда: Пример. Вернемся к предыдущему примеру. Непосредственным подсчетом мы выясним, что число беспорядков D4 = 9. Вычислим D4, используя полученную формулу:
Пример. Вернемся к предыдущему примеру. Непосредственным подсчетом мы выясним, что число беспорядков D4 = 9. Вычислим D4, используя полученную формулу:
Скачать все slide презентации 4. Формула включений-исключений. Беспорядки. 4. Формула включений-исключений. Беспорядки. Теорема 1 (формула включений-исключений). Пусть А А1 А2…Аm – конечное множество. Тогда одним архивом:
