Сочетания с повторениями

Введение

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

Операция

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

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

где nn — количество различных элементов, а kk — количество элементов, избираемых в сочетание.

Свойства

  • Порядок не важен: В сочетаниях с повторениями порядок выбранных элементов не имеет значения.
  • Повторения допустимы: Каждый элемент набора может быть выбран более одного раза.
  • Связь с обычными сочетаниями: Сочетания с повторениями можно представить как нахождение всех возможных уникальных списков длины kk, выбираемых из nn элементов с повторениями.

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

Пример 1

Сколько различных способов можно выбрать 3 шара из ящика с 5 различными шарами, если шары могут быть возвращены после каждого выбора?

C(5+3−1,3)=C(7,3)=7!3!⋅4!=50406⋅24=35\begin{equation*} \begin{aligned} C(5 + 3 - 1, 3) = C(7, 3) \\= \frac{7!}{3! \cdot 4!} = \frac{5040}{6 \cdot 24} = 35 \end{aligned} \end{equation*}

Пример 2

Сколько различных способов можно распределить 4 монетки между 6 копилками?

C(6+4−1,4)=C(9,4)=9!4!⋅5!=36288024⋅120=126\begin{equation*} \begin{aligned} C(6 + 4 - 1, 4) = C(9, 4) \\= \frac{9!}{4! \cdot 5!} = \frac{362880}{24 \cdot 120} = 126 \end{aligned} \end{equation*}

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

  • Что такое сочетания с повторениями?
    • Это способ выбрать элементы из набора, где элементы могут повторяться, а порядок не имеет значения.
  • В чем отличие сочетаний с повторениями от обычных сочетаний?
    • В сочетаниях с повторениями каждый элемент может быть выбран неоднократно, тогда как в обычных сочетаниях элементы выбраны только один раз.

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

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

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