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

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

    flowchart TB
        root[[Подсчет комбинаций]]
        root -->|Использовать базовые правила| rules[Базовые правила]:::featured
        root -->|Свести к типовым комбинациям| configurations[Комбинаторные конфигруации]:::featured

Основные правила

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

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

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

    graph TD
        rules[Базовые правила]:::featured
        rules -->|Разбить на группы| sumRule[Правило суммы]
        rules -->|Поочередно выбирать элементы| productRule[Правило произведения]

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

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

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

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

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

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

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

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

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

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

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

    flowchart TD
        root[Комбинаторная конфигурация]:::featured --> question{{Порядок элементов важен?}}

        question -->|Да| arrangement[Размещение]:::featured
        question -->|Нет| combination[Сочетание]:::featured

        arrangement -->|Без повторений| awr["$\displaystyle  A_n^k = \frac{n!}{(n-k)!}$"]
        arrangement -->|С повторениями| ar["$\displaystyle  \bar{A}_n^k = n^k$"]

        combination -->|Без повторений| cwr["$\displaystyle  C_n^k = \frac{n!}{(n-k)! \ k!}$"]
        combination -->|С повторениями| cr["$\displaystyle  \bar{C}_n^k = C_{n+k-1}^k$"]

        awr -->|Используются все элементы| permutation[Перестановка]:::featured

        permutation -->|Без повторений| pwr["$\displaystyle  P_n = n!$"]
        permutation -.->|С повторениями$^*$| pr["$\displaystyle  P_{n_1, \ \ldots, \ n_k} = \frac{n!}{n_1! \ \ldots \ n_k!}$"]

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