Сочетания без повторений

Введение

Сочетания без повторений — это один из фундаментальных понятий в комбинаторике, используемый для подсчета количества способов выбора kk элементов из набора nn элементов, где порядок выбранных элементов не имеет значения и каждый элемент может быть выбран только один раз. Использование сочетаний без повторений имеет широкий спектр приложений, от статистики до оптимизации процессов.

Операция

Количество сочетаний без повторений из nn элементов по kk определяется следующей формулой:

C(n,k)=n!k!(n−k)!\begin{equation*} \begin{aligned} C(n, k) = \frac{n!}{k!(n-k)!} \end{aligned} \end{equation*}

где n!n! обозначает факториал числа nn, который равен произведению всех положительных целых чисел от 11 до nn.

Свойства

  • Симметрия: C(n,k)=C(n,n−k)C(n, k) = C(n, n-k), то есть количество способов выбрать kk элементов из nn совпадает с количеством способов выбрать n−kn-k элементов.
  • Пределы значений: C(n,0)=C(n,n)=1C(n, 0) = C(n, n) = 1, так как существует только один способ выбрать либо все элементы, либо не выбрать ни одного.
  • Целочисленность: Сочетания выражаются целыми числами, поскольку они представляют собой количество способов выбора элементов.

Примеры использования

Пример 1

Найдите количество способов выбрать 3 элемента из множества из 5 элементов:

C(5,3)=5!3!(5−3)!=5×4×3!3!×2×1=202=10\begin{equation*} \begin{aligned} C(5, 3) = \frac{5!}{3!(5-3)!} \\= \frac{5 \times 4 \times 3!}{3! \times 2 \times 1} = \frac{20}{2} = 10 \end{aligned} \end{equation*}

Пример 2

Найдите количество способов выбрать 2 элемента из 6 элементов:

C(6,2)=6!2!(6−2)!=6×5×4!2!×4!=302=15\begin{equation*} \begin{aligned} C(6, 2) = \frac{6!}{2!(6-2)!} \\= \frac{6 \times 5 \times 4!}{2! \times 4!} = \frac{30}{2} = 15 \end{aligned} \end{equation*}

Часто задаваемые вопросы (FAQ)

  • Что такое комбинаторное число?
    • Комбинаторное число C(n,k)C(n, k) указывает количество способов выбрать kk элементов из nn без учета порядка.
  • Как сочетания без повторений отличаются от сочетаний с повторениями?
    • В сочетаниях без повторений каждый элемент может быть выбран только однажды, тогда как в сочетаниях с повторениями один элемент может быть выбран несколько раз.

Примеры из жизни

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

Ссылки на литературу и ресурсы