Основные формулы комбинаторики

Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно со­ставить из элементов, безразлично какой природы, задан­ного конечного множества. При непосредственном вычис­лении вероятностей часто используют формулы комбина­торики. Приведем наиболее употребительные из них.

Перестановками называют комбинации, состоящие из одних и тех же п различных элементов и отличающиеся только порядком их расположения. Число всех возмож­ных перестановок

где .

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! =1.

Пример 1. Сколько трехзначных чисел можно составить из цифр I, 2, 3, если каждая цифра входит в изображение числа только один раз?

Решение. Искомое число трехзначных чисел

.

Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые от­личаются либо составом элементов, либо их порядком. Число всех возможных размещений

Пример 2. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?

Решение. Искомое число сигналов

.

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отли­чаются хотя бы одним элементом. Число сочетаний

.

Пример 3. Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей?

Решение. Искомое число способов

.

Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством

Замечание. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть элементов одного вида, элементов другого вида и т. д., то число перестановок с повторениями

,

где .

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а объект В может быть выбран n способами, то выбрать либо А, либо В можно m+n способами.

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