Формула включений и исключений. Беспорядки. (Лекция 12)

Сентябрь 13, 2022

Главная
Математика
Формула включений и исключений. Беспорядки. (Лекция 12)

Содержание

2. Формула включений и исключений - конечные множества, тогда Пусть Доказательство: Пусть элемент принадлежит s множествам Тогда
3. Формула включений и исключений Другая формулировка Существует N объектов, каждый из которых обладает или не обладает
4. Задачи 1) В группе 30 студентов, из которых 12 студентов изучают английский, 15 человек французский, 16
5. Задачи 3) 5 джентльменов, вернувшись с вечеринки домой, обнаружили, что надели не свои шляпы. Сколько вариантов
6. Задачи 5) В лифт сели 8 человек. Сколькими способами они могут выйти на четырех этажах так,
7. Задачи 6) Сколькими способами можно переставить цифры числа 12 341 234 так, чтобы никакие две одинаковые
8. Беспорядки
9. Беспорядки Определение 1 Пусть дано множество . Перестановка называется беспорядком, если для любого , то есть
10. Беспорядки Теорема 1. Число беспорядков n-элементного множества равно Доказательство. Обозначим -количество перестановок, у которых на i-том
11. Беспорядки Обозначим - количество перестановок, в которых числа стоят на местах с этими же номерами соответственно,
12. Беспорядки Теорема доказана.
14. Скачать презентацию

Слайд 2

Формула включений и исключений
- конечные множества, тогда
Пусть
Доказательство:
Пусть элемент принадлежит s множествам

Тогда он вносит в левую часть единицу, а в правую – следующее количество единиц

Проверим справедливость равенства

Это равенство верно по следствию 2 из бинома Ньютона.

Слайд 3

Формула включений и исключений
Другая формулировка
Существует N объектов, каждый из которых

обладает
или не обладает свойствами

Пусть - количество объектов , обладающих свойством ,

- количество объектов, не обладающих свойством

Тогда

Слайд 4

Задачи
1) В группе 30 студентов, из которых 12 студентов изучают английский,

15 человек французский, 16 – немецкий язык. 7 человек изучают английский и немецкий, 9 – английский и французский, 6 – немецкий и французский. 4 человека в группе изучают все три языка. Сколько человек в группе не изучают ни одного из перечисленных языков?
2) Найти количество натуральных чисел, не превосходящих 100, которые не делятся ни на 2, ни на 3, ни на 5.

Слайд 5

Задачи
3) 5 джентльменов, вернувшись с вечеринки домой, обнаружили, что надели не

свои шляпы. Сколько вариантов такого беспорядка существует?
4) Сколькими способами можно раздать 5 одинаковых апельсинов, 3 банана, 7 яблок между 4 людьми так, чтобы каждому достался хотя бы один фрукт?

- i–тый человек без фруктов

Слайд 6

Задачи
5) В лифт сели 8 человек. Сколькими способами они могут выйти

на четырех этажах так, чтобы на каждом этаже вышел по крайней мере один человек?
Решение. 8 пассажиров могут распределиться на четырех этажах способами. Из них в
случаях на трех определенных этажах, в случаях на двух определенных этажах, и в 1 – на одном определенном этаже.
По формуле включений-исключений получим

Слайд 7

Задачи
6) Сколькими способами можно переставить цифры числа 12 341 234 так,

чтобы никакие две одинаковые цифры не шли друг за другом?
Решение. Общее число перестановок данных цифр равно P(2,2,2,2). Из них в P(2,2,2,1) перестановках данная цифра стоит два раза подряд (объединили эти две повторяющиеся цифры в один элемент), P(2,2,1,1) повторяются подряд данные две цифры, в P(2,1,1,1) – данные три цифры и в P(1,1,1,1) – данные четыре цифры. По формулу включений-исключений получим
P(2,2,2,2)-4 P(2,2,2,1)+6 P(2,2,1,1)-4 P(2,1,1,1)+ +P(1,1,1,1)=864

Слайд 8

Беспорядки

Слайд 9

Беспорядки
Определение 1
Пусть дано множество . Перестановка
называется беспорядком, если
для

любого , то есть каждое число не стоит на своем месте.
Пример. Пусть . Выпишем все беспорядки:

Слайд 10

Беспорядки
Теорема 1. Число беспорядков n-элементного множества равно
Доказательство. Обозначим -количество перестановок, у

которых на i-том
месте стоит число i. Так как все остальные
(n-1) числа могут стоять произвольно, то
Пусть - количество перестановок, в которых числа i и j стоят на i-м и j-м местах соответственно,

Слайд 11

Беспорядки
Обозначим - количество
перестановок, в которых числа
стоят на местах с

этими же номерами соответственно,
Отметим, что количество наборов
существует .
По формуле включений – исключений получаем

Слайд 12

Формула включений и исключений. Беспорядки. (Лекция 12)

Содержание

Формула включений и исключений- конечные множества, тогдаПустьДоказательство:Пусть элемент принадлежит s множествам

Формула включений и исключенийДругая формулировка Существует N объектов, каждый из которых

Задачи1) В группе 30 студентов, из которых 12 студентов изучают английский,

Задачи3) 5 джентльменов, вернувшись с вечеринки домой, обнаружили, что надели не

Задачи5) В лифт сели 8 человек. Сколькими способами они могут выйти

Задачи6) Сколькими способами можно переставить цифры числа 12 341 234 так,

Беспорядки

БеспорядкиОпределение 1Пусть дано множество . Перестановка называется беспорядком, если для

БеспорядкиТеорема 1. Число беспорядков n-элементного множества равноДоказательство. Обозначим -количество перестановок, у

БеспорядкиОбозначим - количество перестановок, в которых числа стоят на местах с

БеспорядкиТеорема доказана.

Похожие презентации