Перестановки, размещения, сочетания

Комбинаторика - раздел математики, в котором решаются задачи выбора и расположения элементов множеств по заданным правилам.
 
Упорядоченная совокупность из n элементов называется перестановкой из n элементов.
 
Число всех возможных перестановок из n элементов обозначается Рn и вычисляется по формуле: Рn = n ∙ (n - 1) ∙ (n - 2) ∙ ... ∙ 2 ∙ 1. Такое произведение сокращенно записывается как n!.
 
Обратите внимание! Единица факториал равен единице; ноль факториал равен единице.
 
Число всех возможных перестановок из n элементов равно Рn = n!.
 
Упорядоченная совокупность из m элементов, которые выбраны из данных n элементов, называется размещением с n элементов в m.
 
Обратите внимание! Два размещения с n элементов в m различны, если они отличаются или же элементами, или их порядком.
 
Число всех возможных размещений из n элементов в m равна произведению чисел, начиная с числа n, следующими такими, что каждое из следующих на единицу меньше предыдущего и заканчивая числом, на единицу больше разности чисел n и m.
 
Совокупность из m элементов, которые выбраны из данных n элементов, называется комбинацией m элементов в n.
 
Обратите внимание! Две комбинации с n элементов в m различны тогда и только тогда, когда они отличаются хотя бы одним элементом. Порядок элементов значения не имеет.
 
Число всех возможных сочетаний из n элементов в m равен отношению числа размещений из n элементов в m к числу перестановок из m элементов.
 
Правило сложения
 
Если некоторую элементарную действие А можно выполнить т способами, а второе действие В можно выполнить n способами, то действие «либо А, либо В» можно выполнить m + n способами.
 
Правило умножения
 
Если некоторую элементарную действие А можно выполнить m способами, а затем выполнить второе действие Вn способами, то действие «сначала А, потом В» можно выполнить m ∙ n способами.
 
Обратите внимание! При решении комбинаторных задач сначала надо определить, о каком сообщении идет речь в задаче, а затем использовать соответствующую формулу.

Лекция добавлена 28.02.2014 в 13:19:40