Как рассчитать комбинации и перестановки

Предположим, у вас есть n типов элементов, и вы хотите выбрать набор из r. Нам могут понадобиться эти предметы в определенном порядке. Мы называем эти наборы элементов перестановками. Если порядок не имеет значения, мы называем набор комбинаций коллекций. Как для комбинаций, так и для перестановок вы можете рассмотреть случай, когда вы выбираете некоторые из n типов больше, чем один раз, что называется «с повторением», или случай, когда вы выбираете каждый тип только один раз, что называется «нет». репетиция'. Цель состоит в том, чтобы иметь возможность подсчитать количество комбинаций или перестановок, возможных в данной ситуации.

Факториальная функция часто используется при вычислении комбинаций и перестановок. N! означает N × (N – 1) ×... × 2 × 1. Например, 5! = 5×4×3×2×1 = 120. Количество способов заказать набор предметов является факториалом. Возьмите три буквы a, b и c. У вас есть три варианта выбора для первой буквы, два для второй и только один для третьей. Другими словами, всего 3 × 2 × 1 = 6 заказов. В общем, есть n! способов заказать n товаров.

Предположим, у вас есть три комнаты, которые вы собираетесь раскрасить, и каждая из них будет окрашена в один из пяти цветов: красный (r), зеленый (g), синий (b), желтый (y) или оранжевый (o). Вы можете выбирать каждый цвет сколько угодно раз. У вас есть пять цветов на выбор для первой комнаты, пять для второй и пять для третьей. Это дает в общей сложности 5 × 5 × 5 = 125 возможностей. В общем, количество способов выбрать группу из r элементов в определенном порядке из n повторяющихся вариантов равно n ^ r.

Теперь предположим, что каждая комната будет разного цвета. Вы можете выбрать один из пяти цветов для первой комнаты, четырех для второй и всего трех для третьей. Это дает 5 × 4 × 3 = 60, что просто равно 5! / 2!. В общем, количество независимых способов выбрать r элементов в определенном порядке из n неповторяющихся вариантов равно n! / (N – r) !.

Затем забудьте о том, какая комната какого цвета. Просто выберите три независимых цвета для цветовой схемы. Порядок здесь не имеет значения, поэтому (красный, зеленый, синий) такой же, как (красный, синий, зеленый). Для любого пика из трех цветов есть 3! способы их заказа. Таким образом, вы уменьшите количество перестановок на 3! чтобы получить 5! / (2! × 3!) = 10. В общем, вы можете выбрать группу из r элементов в любом порядке из n неповторяющихся вариантов n! / [(N – r)! × r!] Способами.

Наконец, вам нужно создать цветовую схему, в которой вы можете использовать любой цвет сколько угодно раз. Умный бухгалтерский код помогает этой задаче подсчета. Используйте три крестика, чтобы обозначить комнаты. Ваш список цветов представлен как «rgbyo». Смешайте X в своем списке цветов и свяжите каждый X с первым цветом слева от него. Например, rgXXbyXo означает, что первая комната зеленая, вторая зеленая и третья желтая. X должен иметь хотя бы один цвет слева, поэтому для первого X доступно пять слотов. Поскольку список теперь включает X, есть шесть доступных слотов для второго X и семь доступных слотов для третьего X. Всего 5 × 6 × 7 = 7! / 4! способы написания кода. Однако порядок комнат произвольный, поэтому на самом деле существует только 7! / (4! × 3!) Уникальных расположений. В общем, вы можете выбрать r элементов в любом порядке из n повторяемых вариантов (n + r – 1)! / [(N – 1)! × r!] Способами.