Комбинаторика: перестановки, размещения, сочетания

Основы комбинаторики

Комбинаторика — это раздел математики, в котором подсчитывают число способов выбрать или расставить элементы по тем или иным условиям. Такие подсчёты постоянно нужны в теории вероятностей: чтобы найти вероятность события, часто требуется сначала сосчитать число благоприятных и общее число равновозможных исходов. В основе всей комбинаторики лежит правило умножения.

Если первый выбор можно сделать m способами, а после него второй — k способами, то оба выбора вместе можно сделать m * k способами.

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

На основе правила умножения вводят три ключевых понятия. Знак n! (читается «эн факториал») означает произведение всех натуральных чисел от 1 до n; по определению 0! = 1.

• Перестановки из n элементов — это всевозможные упорядоченные наборы из всех n элементов: P_n = n!.
• Размещения — упорядоченные наборы по k элементов, выбранные из n; здесь важен и состав, и порядок.
• Сочетания — наборы по k элементов из n, в которых порядок не важен, важен только состав.

Разобранный пример

Сколькими способами можно расставить на полке 4 разные книги? Здесь берут все элементы и важен порядок, поэтому это перестановки:

P_4 = 4! = 4 * 3 * 2 * 1 = 24 способа.

А сколькими способами выбрать 2 книги из 4, если порядок выбора не важен? Это сочетания:

C = 4! / (2! * (4 - 2)!) = 24 / (2 * 2) = 6 способов.

Если бы порядок был важен (например, одна книга идёт в подарок, другая остаётся), мы считали бы размещения: A = 4! / (4 - 2)! = 24 / 2 = 12 способов.

Как выбрать нужную формулу

Главный вопрос при решении задачи: важен ли порядок элементов. Если да — это перестановки или размещения, если нет — сочетания. Если берут сразу все элементы, это перестановки.

Применение в задачах на вероятность

Комбинаторика напрямую помогает считать вероятности. Например, чтобы найти вероятность вытащить два определённых шара из урны, нужно поделить число благоприятных сочетаний на общее число сочетаний. Так комбинаторные формулы становятся инструментом для классического определения вероятности, где P = m / n, а числа m и n как раз подсчитывают с помощью перестановок, размещений или сочетаний. Поэтому уверенное владение этими формулами — необходимый шаг перед решением вероятностных задач.

Частые ошибки. Путают размещения и сочетания, не задумавшись, важен ли порядок; неверно считают факториал; ошибочно полагают, что 0! = 0, тогда как 0! = 1.

Кратко о главном

• Правило умножения: m * k способов для двух последовательных выборов.
• Перестановки из n элементов: P_n = n!.
• В размещениях порядок важен, в сочетаниях — нет.
• Факториал — произведение всех натуральных чисел до n, причём 0! = 1.