Комбинаторика_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. Размещения без повторения