🗊Презентация Комбинаторика. Правило суммы

Дискретная математика Комбинаторика

Правило суммы Классическая формулировка Если элемент α можно выбрать k способами, а элемент β можно выбрать m способами. Тогда или можно выбрать k +m способами.

Теорема о мощности объединения множеств (современная формулировка) Теорема о мощности объединения множеств (современная формулировка) Количество элементов объединения двух множеств равно сумме количества элементов в первом и во втором множестве, за вычетом количества элементов их пересечения:

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

Для трех множеств теорема имеет вид: Для трех множеств теорема имеет вид:

Пример: Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Пример: Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?

Правило произведения Классическая формулировка Если элемент α можно выбрать k способами, а элемент β можно выбрать m способами. Тогда пару α и β можно выбрать km способами.

Теорема о мощности прямого произведения множеств (современная формулировка) Теорема о мощности прямого произведения множеств (современная формулировка)

Пример: Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 6 экземпляров учебника физики, надо выбрать комплект, содержащий все учебники по одному разу. Сколькими способами это можно сделать?

Пример: Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: а) все цифры были разными; б) на последнем месте четная цифра.

Число размещений без повторений Число размещений без повторений из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k различными координатами. Число размещений без повторений находится по формуле: Пример: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?

Число размещений с повторениями Число размещений с повторениями из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k координатами, среди которых могут быть одинаковые. Число размещений с повторениями находится по формуле: Пример: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?

Число перестановок без повторений Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов. Число перестановок без повторений находится по формуле:

Задача на рассадки и расстановки В задачах на рассадки и расстановки используется тот факт, что n элементов на n местах можно расставить n! различными способами

Пример Сколькими способами можно расставить на книжной полке 5 различных книг? В скольких случаях две определенные книги А и В окажутся рядом? Всего вариантов расстановки 5 книг на 5 местах : 5!=120

Замечание: где – число способов выбрать нужные места; – число способов расположить на них нужные элементы; – число способов расположить остальные элементы на оставшихся местах.

Схема расстановки:

Число сочетаний без повторений Число сочетаний без повторений из n по k – это число способов, сколькими можно из n различных элементов выбрать k штук без учета порядка. Число сочетаний без повторений находится по формуле:

Свойства 1) 2) 3) 4) 5) 6) 7)

Урновая задача Урновая задача – это задача, в которой производится выбор сразу нескольких элементов из заданной совокупности. Пример: В урне 7 шаров. Из них 3 белых, 4 черных. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет: 1) один белый; 2) два белых; 3) все белые.

Схема урновой задачи

Общее число исходов эксперимента найдем по общей формуле

Количество элементов множества А1 найдем по формуле:

Количество элементов множества А2 найдем по формуле:

Количество элементов множества А3 найдем по формуле:

Выучить или переписать в тетрадь определения на слайдах 2-5, 7, 8, 11-14, 16, 18, 19, 21