1. Общие правила комбинаторики
Комбинаторикой называется раздел математики, изучающий способы подсчета всевозможных комбинаций из некоторых элементов (объектов), составленных по определенным правилам.
Термин «комбинаторика» происходит от латинского слова «combina», что в переводе означает «сочетать», «соединять».
Правило произведения:
Если объект A может быть выбран m различными способами, причем после каждого такого выбора объект B можно выбрать n различными способами, то выбор «сначала A, а потом B» можно осуществить m⋅n способами.
Обобщение правила произведения:
Если объект A1 может быть выбран m1 различными способами, причем после каждого выбора объекта A1 объект A2 может быть выбран m2 различными способами, причем после каждого выбора объектов A1, A2, …, Ak–1 объект Ak может быть выбран mk различными способами, то выбор «сначала A1, потом A2, A3, ..., Ak–1, Ak» можно осуществить m1⋅m2... mk способами.
Правило суммы:
Если объект A может быть выбран m различными способами, а другой объект B можно выбрать n различными способами, причем ни один из способов выбора объекта A не совпадает ни с одним из способов выбора объекта B, то выбор «либо A, либо B» можно осуществить m+n способами.
Замечание (правило суммы 2):
Если некоторые способы выбора объектов A и B совпадают и число совпадений равно k, то общее число различных способов выбора либо объекта A, либо В равно m+n−k.
2. Вычисление числа перестановок. Перестановки без повторений
Перестановками из n различных элементов называются соединения (наборы), каждое(ый) из которых содержит эти n элементов, взятых в определенном порядке.
Замечание 1. Перестановкой из n элементов можно считать установленный в конечном множестве порядок.
Число всех пeрестановок из n элементов обозначается Pn (от французского слова «реrmutation» – перестановка).
Замечание 2. Различные перестановки из n данных элементов отличаются друг от друга только порядком расположения элементов.
Выведем формулу для подсчета числа перестановок из n элементов.
Вывод формулы:
Пусть имеется n различных элементов, которые нужно распределить по n местам. Выбор первого элемента можно осуществить n способами (иначе говоря, на первое место можно поставить любой из n элементов).
После выбора первого элемента второй элемент можно выбрать (n − 1) способом (на второе место можно поставить любой из оставшихся элементов, их осталось (n − 1)), третий элемент можно выбрать (n − 2) способами и т. д. Последний элемент − одним способом.
По правилу произведения n элементов можно выбрать n ⋅ (n − 1) ⋅ (n − 2) ⋅(n − 3) ⋅ …⋅ 1 способом, т.е. число способов равно произведению всех натуральных чисел от 1 до n.
Для такого произведения применяют специальное обозначение: n! (читается «эн факториал»).
Таким образом, число перестановок из n элементов равно Pn =n!
3. Вычисление числа размещений. Размещения без повторений
Размещениями из n различных элементов по m называются соединения (наборы), каждое(ый) из которых содержит m элементов из n, взятых в определенном порядке.
Размещения из n различных элементов по m отличаются друг от друга элементами или порядком их расположения.
Число всех размещений из n элементов по m обозначается (от французского слова «arangent» – размещение, приведение в порядок).
Число всех размещений из n различных элементов по m можно вычислить по формуле:
4. Вычисление числа сочетаний. Сочетания без повторений
Сочетаниями из n различных элементов по m называются соединения (наборы), каждое(ый) из которых содержит m элементов из n.
Сочетания из n различных элементов по m отличаются друг от друга только элементами. Порядок следования элементов не учитывается.
Число всех сочетаний из n элементов по m обозначается (от французского слова «combination» – сочетание).
Число всех сочетаний из n различных элементов по m можно вычислить по формуле:
5. Перестановки с повторениями
Если некоторые из n элементов множества равны, т. е. n = n1 + n2 +…+nk, то число перестановок из n элементов равно:
Рассмотрим перестановку из n элементов, среди которых некоторые одинаковые, пусть таких n1 – одинаковых. Тогда при перестановке этих n1 элементов между собой перестановка из n элементов останется той же, а число всех перестановок из n элементов уменьшится во столько раз, сколькими способами можно переставить n1 элементов, т. е. в n 1! раз. Аналогично рассмотренному: если среди n элементов есть еще n2 – одинаковых, то число всех перестановок из n элементов уменьшится в n 2! раз и т. д. Таким образом, общее число перестановок из n элементов с повторениями вычисляется по формуле:
Размещения с повторениями
Размещения из n элементов, в каждое из которых входит m элементов, причем один и тот же элемент может повторяться в каждом размещении любое число раз, называются размещениями из n элементов по m элементов с повторениями.
Число размещений с повторениями обозначается и может быть вычислено по формуле:
Выбор первого элемента можно осуществить n способами (на первое место можно поставить любой из n элементов).
После выбора первого элемента второй элемент можно выбрать n способами (на второе место можно поставить также любой из n элементов, так как элементы в перестановке с повторениями могут повторяться), третий элемент можно выбрать также n способами и т. д., m-й элемент – n способами.
По правилу произведения m элементов из n можно выбрать n ⋅ n ⋅ n ⋅ n ⋅ ... ⋅ n (число сомножителей равно m) способами, т. е. число размещений с повторениями может быть вычислено по формуле:
Сочетания с повторениями
Сочетаниями из n элементов по m c повторениями называются соединения, содержащие m элементов (без учета порядка следования), причем любой элемент может входить в соединение некоторое число раз, не большее m.
Число сочетаний из n элементов по m с повторениями обозначают
Формула для вычисления числа сочетаний из n элементов по m с повторениями:
Элементы комбинаторики и бином Ньютона
