Файл: Элементы комбинаторики.ppt

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

Комбинаторика - раздел математики, в котором изучаются простейшие «соединения»: перестановки, размещения, сочетания. Происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».

ПРАВИЛО СУММЫ

Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами.
При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В.
Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k—число совпадений.





Задача 1. В коробке находится 10 шаров: 3 белых, 2 черных, 1 синий и 4 красных. Сколькими способами можно взять из ящика цветной шар?





Решение:
Цветной шар – это синий или красный, поэтому применим правило суммы:

ПРАВИЛО ПРОИЗВЕДЕНИЯ

Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами.
При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.





Задача 2. Сколько может быть различных комбинаций выпавших граней при бросании двух игральных костей?


Правила суммы и произведения верны для любого количества объектов.





Решение:
На первой кости может быть: 1,2,3,4,5 и 6 очков, т.е. 6 вариантов.
На второй – 6 вариантов.
Всего: 6∙6=36 вариантов.

факториал

Произведение всех натуральных чисел от 1 до n включительно называют n- факториалом и пишут n!.

---

ВАЖНО: 0!=1

Перестановки

Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов.

Сочетания

Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Размещения

Размещением из n элементов по m называется упорядоченный набор из m различных элементов некоторого n-элементного множества.





23.05.23





Составить несколько комбинаций (выборок)


Перестановки


Размещения


Повторяются ли элементы в выборке?


Схема определения вида комбинации



да нет


да нет


Сочетания


Важен ли
порядок элементов?


Все ли элементы
входят в выборку?


нет

---