Similar presentations:
Комбинаторика_1
1.
КомбинаторикаКомбинаторные
принципы
2.
КомбинаторикаРаздел дискретной математики, изучающий
способы подсчета и перебора
комбинаторных объектов
Комбинаторный объект – элемент
некоторого конечного множества,
обладающий определенными свойствами. В
большинстве случаев состоит из отдельных
элементов («составных частей»)
Множество комбинаторных объектов может
быть задано описанием их свойств либо
алгоритмом их построения
3.
Комбинаторные принципыДва основных принципа
1. Принцип сложения
Если все множество комбинаторных объектов C можно
разбить на два непересекающихся подмножества A и
B (иными словами, есть два разных способа
(алгоритма) построения объекта c C), то |C| = |A| + |B|
2.
Принцип умножения
Если каждый комбинаторный объект c C состоит из
двух независимых частей: a A и b B (иными словами,
алгоритм построения объекта c состоит из двух
независимых шагов), то |C| = |A| * |B|
4.
Комбинаторные принципы. ПримерНа зимние каникулы мы хотим съездить в СанктПетербург и мы уже забронировали гостиницу на
определенную дату. Сколько существует способов
добраться?
a. Мы хотим попасть в Санкт-Петербург напрямую, без
пересадок. Имеется 3 подходящих авиарейса и 4
поезда.
b. В Москве у нас есть друг, с которым мы хотели бы
встретиться и провести 1 день. При этом мы
решили до Москвы долететь самолетом, а от
Москвы до Санкт-Петербурга доехать поездом. Есть
4 подходящих самолета Пермь – Москва и 5
поездов Москва – Санкт-Петербург на след. день.
5.
Комбинаторные принципы. Пример 2На Новый год вы решили всем своим одногруппникам
сделать небольшие подарки. Вы решили, что подарком
будет либо шоколадка, либо пакетик сока.
Одногруппники у вас очень капризные и расстроятся,
если у кого-то подарки будут одинаковыми. В магазине
вы нашли 8 подходящих видов шоколадок и 6 сортов
сока. Можно ли сделать всем разные подарки? В
группе учится 25 человек.
6.
Комбинаторные принципыДополнительный принцип
3. Принцип вычитания
Если U – это множество всех объектов («универсум»),
A – множество комбинаторных объектов,
удовлетворяющих некоторому условию, а
B – множество объектов, не удовлетворяющих этому
условию, то
|A| = |U| - |B|
7.
КомбинаторикаКомбинаторные
операции
8.
Повторные выборкиA = {a1, …, an} – множество некоторых элементов
Множество конечно, все элементы различны
Выборка – элементарная операция, выбор одного
элемента из A
Повторная выборка – это выполненная k раз операция
выборки, то есть выбор k элементов из множества A
Для повторной выборки необходимо уточнить два
условия:
1. Возвращаются ли элементы обратно в A после того,
как будут выбраны.
2. Важен ли порядок выбора элементов.
Получаем 4 варианта повторных выборок, которые
называются комбинаторными операциями
9.
Комбинаторные операцииПовторные выборки с учетом порядка размещения
1. Размещения без повторения