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

В математике есть различные стратегии для определения количества способов выбора объектов из заданного множества. Сколькими способами мы можем выбрать 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 возможных способов бросить кубик. Поскольку вы можете выполнять обе задачи одновременно, есть 2 × 6 = 12 способов подбросить монету и бросить кубик.

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

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

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

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}}

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

Сочетание

Число возможных способов выбрать 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

Каковы могут быть сочетания букв A, B, C и D в группе из 3 букв? Существует 24 возможных варианта, если порядок важен. В комбинаторном счете порядок не имеет значения. Только первый ряд имеет значение, и существует 4 возможных сочетания.

ABC	ABD	ACD	BCD
ACB	ADB	ADC	BDC
BAC	BAD	CAD	CBD
BCA	BDA	CDA	CDB
CAB	DAB	DAC	DBC
CBA	DBA	DCA	DCB

Вместо того чтобы перечислять все возможные сочетания, мы можем подсчитать количество возможных сочетаний, порядок элементов в которых не важен, используя формулу, приведенную выше. Здесь имеется 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}

Примерное пространство событий, показывающее все возможные размещения, показано ниже:

A на 1 месте	B на 1 месте	C на 1 месте	D на 1 месте
ABCD	BACD	CABD	DABC
ABDC	BADC	CADB	DACB
ACBD	BCAD	CBAD	DBAC
ACDB	BCDA	CBDA	DBCA
ADBC	BDAC	CDAB	DCAB
ADCB	BDCA	CDBA	DCBA

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

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

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

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