Комбинаторика. Принципы и основные комбинаторные соединения

1. Комбинаторика

Принципы и основные
комбинаторные соединения

2.

КОМБИНАТОРНЫЕ ПРИНЦИПЫ
ПРИНЦИП СУММЫ
ПРИНЦИП ПРОИЗВЕДЕНИЯ
Если элемент х из множества Х можно выбрать
m способами, элемент у из множества Y
можно выбрать n способами, причем любой
способ выбора у не зависит от любого
способа выбора х, то выборку "х или у"
можно осуществить (m + n) способами.
Если элемент х из множества Х можно
выбрать m способами, и после каждой такой
выборки элемент у из множества Y можно
выбрать n способами, то выборку "х и у"
можно осуществить (m·n) способами.
КОМБИНАТОРНЫЕ СОЕДИНЕНИЯ
Х
А
Р
А
К
Т
Е
Р
В
Ы
Б
О
Р
К
И
с повторениями
упорядоченная
m - любое
без повторений
упорядоченная
без повторений
упорядоченная
m=n
без повторений
неупорядоченная
с повторениями
упорядоченная
m=m1+m2+…+mk
c повторениями
неупорядоченная
Размещения с
повторениями
Размещения без
повторений
Перестановки
без
повторений
Сочетания
без
повторений
Перестановки
с повторениями
данного состава
Сочетания
с
повторениями
~m
An n m Аnm
n!
(n m)!
Pn n!
Ч И С Л О
Cnm
n!
~ m (n m 1)!
m!
Pm
C m! (n 1)!
m!(n m)!
m1 ! m 2 ! ... m n ! n
В Ы Б О Р О
К

3. Алгоритм решения комбинаторной задачи

1. Установить тип КБЗ:
Если в условии дано одно множество и на выборку не накладываются
дополнительные условия, кроме характеристики выборки, то это простая
КБЗ;
Если в условии дано более одного множества или на выборку накладываются
дополнительные условия, то задача сложная.
2. Если задача простая , то:
2.1. Записать множество, из которого производится выборка:
Х = {х1, х2 ,…, хn}, где n (Х) = n;
2.2. Записать выборку и установить ее длину m;
2.3. Установить характер выборки
2.4. Определить вид комбинаторного соединения и формулу для подсчета.
2.5. Используя формулу, вычислить число выборок.
Если задача сложная, то:
2.1. Сформулировать все простые задачи, на которые разбивается данная
сложная КБЗ;
2.2. Решить каждую КБЗ простую задачу;
2.3.Установить, какое правило (Пр , ПрП) использовать для решения.
2.4. Применить правила, установленные в п.2.3, осуществить вычисления