Калькулятор сочетаний

В комбинаторике существуют различные математические стратегии для определения количества способов выбора объектов из заданного множества. Сколькими способами можно выбрать r элементов из n возможных? Ответ зависит от того, имеет ли значение порядок их расположения и допускаются ли повторения.

Количество способов выбрать r неупорядоченных элементов из множества n называется сочетанием (combination) и обозначается как C(n, r). Это значение также известно как биномиальный коэффициент. Наш онлайн-калькулятор сочетаний позволяет быстро и точно вычислить количество возможных комбинаций r объектов из набора в n элементов.

Правила использования калькулятора сочетаний

Для любого заданного множества объектов существует определенное количество способов выбрать или сгруппировать их часть (или все сразу) в соответствии с заданными условиями. Данный калькулятор вычисляет количество способов выбора r объектов из набора n элементов без повторений и в случаях, когда порядок не имеет значения. Для расчета требуются две переменные:

• n = общее количество доступных объектов для выбора;
• r = количество выбираемых объектов (позиций для заполнения).

Обязательным математическим условием для ввода данных в калькулятор сочетаний является следующее неравенство:

$$0 ≤ r ≤ n$$

Если вы введете значение r, превышающее n, калькулятор выдаст системное сообщение:

"Пожалуйста, введите 0 ≤ r ≤ n".

Фундаментальные принципы вычислений

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

Правило суммы

Если первая задача может быть выполнена m способами, а вторая — n способами, и при этом они не могут выполняться одновременно, то общее количество способов выполнить любую из этих задач равно (m + n).

Правило произведения

Если первая задача выполняется m способами, а вторая — n способами, и обе задачи могут происходить одновременно (или последовательно), то существует (m × n) способов их совместного выполнения.

Примеры

В кафетерии продаются 3 вида выпечки и 4 вида напитков. Среди выпечки — пирожки с яблоками, клубникой и черникой. Напитки — апельсиновый, виноградный, вишневый и ананасовый соки. И напитки, и пирожки стоят по 2 доллара. У вас с собой ровно 2 доллара, то есть вы можете купить только что-то одно. По правилу суммы у вас есть 3 + 4 = 7 возможных вариантов сделать выбор.

Предположим, вы хотите подсчитать количество исходов при одновременном подбрасывании монеты и игральной кости (кубика). У монеты две стороны, поэтому способов ее падения — 2. У классического кубика 6 граней, то есть 6 возможных исходов. Поскольку эти действия выполняются вместе, по правилу произведения существует 2 × 6 = 12 возможных вариантов исхода.

Если вы хотите вытянуть 2 карты из стандартной колоды в 52 карты без возврата, то для первой карты существует 52 варианта, а для второй — уже 51. Следовательно, общее количество способов вытянуть две карты составляет 52 × 51 = 2 652.

Пространства событий

Пространство событий (или пространство элементарных исходов) — это перечень всех возможных результатов испытания, который традиционно обозначается заглавной буквой S. Пространство событий для одновременного подбрасывания монеты (где H — орел, T — решка) и бросания игральной кости выглядит так:

S = {{H,1}, {H,2}, {H,3}, {H,4}, {H,5}, {H,6}, {T,1}, {T,2}, {T,3}, {T,4}, {T,5}, {T,6}}

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

Сочетания

Число возможных способов выбрать r уникальных (неповторяющихся) элементов из n возможных, когда порядок их расположения не имеет значения, называется сочетанием. Сочетание объектов математически записывается как C(n, r). Формула для вычисления сочетаний выглядит следующим образом:

$$C(n,r)=\frac{n!}{r!(n-r)!}$$

Знак ! после числа или переменной означает факториал. Например, n! — это факториал числа n, то есть произведение всех натуральных чисел от 1 до n. Факториал 2! — это 1 × 2. Факториал 3! — это 1 × 2 × 3. Факториал 4! — это 1 × 2 × 3 × 4. Факториал 5! — это 1 × 2 × 3 × 4 × 5, и так далее. Важно помнить, что факториал определен только для целых неотрицательных чисел.

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

Пример 1

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

{1, 2, 3, 4}

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

Если бы порядок расположения элементов имел значение, мы бы использовали формулу для размещений, и получили бы следующий перечень:

(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)

Но поскольку порядок не важен, мы ищем именно сочетания. Уникальные пары будут выглядеть так:

(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)

Получается 6 возможных сочетаний. Чтобы не расписывать все варианты, можно использовать формулу. В данном примере n = 4, r = 2. Следовательно:

$$C(4,2)=\frac{4!}{2!(4-2)!}=\frac{4!}{2!2!}=\frac{4 × 3 × 2 × 1}{(2× 1)(2× 1)}=\frac{24}{4}=6$$

Именно этот алгоритм использует наш калькулятор для выдачи мгновенного результата.

Пример 2

Сколько комбинаций из 3 букв можно составить из набора A, B, C и D? Если бы порядок был важен, мы получили бы 24 возможных варианта. Однако в комбинаторике сочетаний порядок не учитывается. Значение имеет только уникальный состав группы, поэтому существует всего 4 возможных сочетания (первый столбец в таблице).

Вместо составления громоздких таблиц мы можем рассчитать количество возможных комбинаций без учета порядка с помощью формулы. Здесь у нас есть n = 4 объекта, из которых мы выбираем r = 3. Следовательно:

$$C\left(n,r\right)=C\left(4,3\right)=\frac{4!}{\left(4-3\right)!3!}=\frac{4!}{1!3!}=4$$

Размещения

Размещение (permutation) определяет количество способов выбора и организации объектов, когда порядок их расположения имеет значение. Формула для вычисления числа размещений при выборе r объектов из списка в n элементов имеет следующий вид:

$$P\left(n,r\right)=\frac{n!}{\left(n-r\right)!}$$

Две главные характеристики размещений: повторение объектов не допускается, а порядок элементов строго важен.

Пример 3

Предположим, что в собеседовании участвуют 4 кандидата. Задача отборочной комиссии — распределить их по рейтингу от 1 до 4 места. Вот как распределяются варианты:

• 1-е место — 4 варианта выбора
• 2-е место — 3 варианта выбора
• 3-е место — 2 варианта выбора
• 4-е место — остается 1 вариант

Правило произведения дает нам общее число способов распределения мест: 4 × 3 × 2 × 1 = 24, что математически равно 4!. Допустим, кандидаты обозначены буквами:

{A, B, C, D}

Пространство элементарных исходов, демонстрирующее все возможные размещения, показано в таблице ниже:

Чтобы не перечислять все возможные варианты расстановки вручную, мы можем быстро подсчитать их количество с помощью формулы размещений. В этом примере дано n = 4 кандидата, и мы распределяем все r = 4 места одновременно. Следовательно:

$$P\left(n,r\right)=P\left(4,4\right)=\frac{4!}{\left(4-4\right)!}=\frac{4!}{0!}=24$$

Разница между сочетаниями и размещениями

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