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

Раздел 3. Элементы комбинаторики

Метод математической индукции

Метод доказательства, называемый методом математической индукции, основан на следующем принципе, который является одной из аксиом арифметики натуральных чисел.

Предложение , зависящее от натуральной переменной , считается истинным для всех , если выполнены следующие два условия:

а) предложение истинно для

б) из предположения, что истинно для (где -любое натуральное число), следует, что оно истинно и для следующего значения , т. е. для .

Этот принцип называется принципом математической индукции.

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

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

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

,

где .

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

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

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

.

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

.

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

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

.

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

.

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

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

.

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

.

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

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

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

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