Основные правила и формулы комбинаторики
Основные правила комбинаторики
Во многих случаях для того, чтобы подсчитать число всех возможных исходов опыта, нужно перебрать огромное количество вариантов. Чтобы формализовать эту задачу и правильно подсчитать общее число опытов используют комбинаторные формулы.
Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из конечного множества данных объектов.
При выводе комбинаторных формул руководствуются двумя правилами.
1) Правило суммы.
Если объект 
можно выбрать 
способами, а объект B – k способами, то объект либо , либо 
можно выбрать 
способами.
Пример. В корзине лежат белые, синие и красные шары. Если синих шаров 5, а красных – 7, то цветной шар (либо красный, либо синий) можно выбрать 7 + 5 = 12 способами.
2) Правило произведения.
Если объект можно выбрать способами, а объект – 
способами, то пару 
можно выбрать 
способами.
Пример. Подарочный набор состоит из флакона духов и помады. Имеются духи трех видов, помада — пяти тонов. Сколько различных наборов можно составить? Так как каждый из трех видов духов можно дополнить помадой 5 цветов, то всего получится 
вариантов подарочных наборов.
Теперь перейдем к рассмотрению и подсчету числа различных комбинаций.
Формула размещений без повторений
Размещения без повторений получаются по следующей схеме. Имеется n различных предметов. Из них выбирают 
предметов так, что меняется и состав выбранных предметов и порядок их расположения относительно друг друга. Представить такую ситуацию можно следующим образом. Рисуем ряд из клеток
| .......... | m |
Берем произвольный предмет из 
имеющихся и помещаем в первую клетку (это можно сделать способами), затем берем любой из оставшихся 
предметов и помещаем во вторую клетку ( способами). Значит, по правилу произведения, пару — первую и вторую клетку — можно заполнить () способами. Рассуждая аналогично, найдем, что число способов разместить предметов из в клетках — число размещений из по обозначаемое 
, равно
.
Используя обозначения 
и 
формулу для размещений можно переписать по-другому:
.
Пример. Коротышки, проживающие в Цветочном городе, решили провести выборы городского начальства: мэра, вице-мэра, казначея, полицмейстера. Договорились, что каждый коротышка может претендовать на любой пост, но может быть выбран только на один пост. Сколькими способами можно выбрать городское начальство, если в городе 100 коротышек?
В этой задаче = 100, = 4. Первый пост – мэра, может занять любой из 100 жителей, вице-мэром может стать любой из оставшихся 99, казначеем – один из 98, и, наконец, полицмейстером любой из 97. Всего способов выбрать начальство:
.
Формула перестановок
Перестановки получаются, если различных предметов располагать в различном порядке (например, книги на полке). Число перестановок из предметов, обозначаемое 
, можно найти, если в предыдущей схеме размещений считать, что 
. Тогда
Пример. Из цифр 1, 2, 3, 5 составляются всевозможные четырехзначные числа так, чтобы цифры не повторялись. Сколько чисел можно составить?
Так как цифры не могут повторяться, значит, различные числа могут различаться только расположением цифр, т.е. число перестановок из различных цифр: 
.
Формула сочетаний без повторений
Такая комбинация получается, если при выборке предметов из важен только состав выборки, а не порядок расположения элементов выборки. Например, если коротышки из Цветочного города будут выбирать не начальство, где важно, кто какой пост занимает, а делегацию из четырех коротышек для поездки в Солнечный город, в которой важен только состав.
Число сочетаний из объектов по обозначается 
. Найдем его, используя следующее соображение. Чтобы получить все возможные размещения нужно взять выборку из предметов по определенного состава и произвести в ней все возможные перестановки. Затем взять другой состав и снова переставить и т.д.
Тогда число размещений (по правилу произведения) будет равно
,
откуда для числа сочетаний получим:
.
Число сочетаний используется в формуле бинома (двучлена) Ньютона
и поэтому еще называется биномиальным коэффициентом.
Пример. Подсчитаем, сколько различных делегаций из четырех коротышек можно составить для поездки в Солнечный город. Здесь = 100, = 4, поэтому количество делегаций равно
.