Формула числа сочетаний с повторениями

Раньше мы выяснили, что число способов разложить $k$ различных шаров по $n$ ящикам есть число размещений с повторениями $\overline{A}_n^k=n^k.$

А сколько получится способов, если шары одинаковые (в ящике может быть любое число шаров)?

Поступим следующим образом. Обозначим шары нулями, их будет $k$, а также введем $n-1$ единиц, которые будут обозначать "перегородки". Тогда любая последовательность из $k$ нулей и $n-1$ единиц однозначно зафиксирует способ разложения шаров: число нулей до первой единицы - это число шаров в первом ящике, число нулей между первой и второй единицей - это число шаров во втором ящике и так далее. А расставить $k$ единиц в последовательности из $k+n-1$ объектов можно (мы уже знаем - это число сочетаний)

$$\overline{C}_n^k=C_{k+n-1}^k=\frac{(k+n-1)!}{(n-1)!\cdot k!}$$

способами.

Эта формула носит название числа сочетаний с повторениями из $n$ объектов по $k$. Она описывает, сколькими способами можно составить комбинацию по $k$ элементов из элементов $n$ типов (элементы в комбинации могут повторяться, но порядок их не важен).

Примеры решений

Рассмотрим решение типовых задач.

Пример 1. В магазине продаются булочки трех видов: с маком, изюмом и повидлом. Мама послала Колю купить 6 булочек. Сколько возможных вариантов выбора у него есть?

Решение. По условию задачи требуется составить комбинацию из $k=6$ элементов, которые выбираются (возможны повторения) из объектов $n=3$ типов (с маком, изюмом, или повидлом). Всего возможных наборов булочек будет (по формуле сочетаний с повторенями):

$$\overline{C}_3^6=C_{3+6-1}^6=C_{8}^6=\frac{8!}{2!\cdot 6!}=28.$$

Пример 2. Сколько решений в неотрицательных числах имеет уравнение $x+y+z+q=8?$

Решение. Переформулируем задачу в терминах шаров и ящиков (см. выше вывод формулы). Пусть у нас есть $k=8$ шаров/единичек, их нужно разместить в $n=4$ ящиках (каждый ящик - это слагаемое в выражении слева, вместе как раз шаров во всех ящиках будет 8, то есть равенство выполнится). Так как решение требуется в неотрицательных числах, то ящик в том числе может быть пустым (дополнительных ограничений нет). Применяем формулу числа сочетаний с повторениями:

$$\overline{C}_4^8=C_{4+8-1}^8=C_{11}^8=\frac{11!}{3!\cdot 8!}=165.$$

Найти сочетания с повторениями из n по k

Чтобы вычислить число сочетаний с повторениями $\overline{C}_n^k$ онлайн, используйте калькулятор ниже.

Видеоролик о сочетаниях с повторениями

Не все понятно? Посмотрите наш видеообзор для формулы сочетаний с повторениями: как использовать Excel для нахождения числа сочетаний, как решать типовые задачи.

Расчетный файл из видео можно бесплатно скачать

Полезные ссылки

• Онлайн учебник по теории вероятностей
• Основные формулы комбинаторики
• Примеры решений задач по теории вероятностей
• Заказать свои задачи на вероятность

Решебник с задачами по комбинаторике и теории вероятностей: