Формулы комбинаторики

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

Базовые правила

Вся комбинаторика строится на двух основных правилах: правиле суммы и правиле произведения.

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

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

Ещё правила часто используют в роли «связующего клея» между комбинаторными конфигурациями.

Комбинаторные конфигурации

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

Такие полезные виды комбинаций называют типовыми комбинациями или, по-умному, комбинаторными конфигурациями. В их число входят размещения, перестановки, сочетания и другие, более редкие виды.

Все основные типовые комбинации мы уже детально изучили и закрепили задачами по-отдельности. Теперь нужно из отдельно рассмотренных кусочков составить у себя в голове общую и цельную картину или схему основных формул базовой комбинаторики.

Построение схемы

Во время составления комбинаций сразу возникает вопрос: а важен ли порядок расположения элементов? Считать ли разными комбинации, состоящие из одних и тех же элементов, но расставленных в разном порядке?

Мы уже встречались как с задачами, в которых порядок элементов имеет значение, так и с задачами, в которых важны только выбранные элементы.

Два ответа на вопрос о важности порядка элементов («Да» и «Нет») порождают две базовые комбинаторные конфигурации: размещения и сочетания. Каждая из них разделяется на две формулы в зависимости от того, можно ли использовать один и тот же элемент повторно.

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

Схема основных комбинаторных конфигураций с формулами:

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