О калькуляторе
Этот инструмент считает число сочетаний с повторениями. Он пригодится в задачах, где нужно узнать количество способов набрать группу из предметов, если порядок элементов не важен, а сами объекты внутри набора можно выбирать несколько раз.
Пользоваться калькулятором можно двумя способами. Вы можете просто указать числовой размер исходного множества или переключиться в текстовый режим и ввести конкретный набор букв или символов (длиной до 100 знаков). После этого укажите, сколько именно объектов вы хотите выбрать. В отличие от обычных сочетаний, здесь длина выборки может превышать размер самого множества — например, можно выбрать 10 букв из 3 доступных.
На странице действует единственное важное ограничение: сумма значений в обоих полях ввода должна быть не больше 10 000. Расчет выполняется по формуле: $$\bar{C}_n^k = C_{n+k-1}^k = \frac{(n+k-1)!}{k! \cdot (n-1)!}$$
Калькулятор выводит подробный пошаговый ход решения. Для удобства чтения большие результаты разделяются пробелами по разрядам, а огромные числа переводятся в научный формат со степенями. Если вы считали задачу в текстовом режиме, и итоговых комбинаций получилось меньше 100, ниже на странице откроется полный нумерованный список всех возможных наборов.
Теория: Сочетания с повторениями
В комбинаторике часто приходится сталкиваться с задачами, где нужно выбрать определенное количество предметов из нескольких доступных видов. При этом предметы одного вида абсолютно одинаковы, их количество не ограничено, а порядок, в котором мы складываем их в общий набор, совершенно не важен.
- Сочетанием с повторениями из $n$ элементов по $k$ называется любой неупорядоченный набор, состоящий из $k$ элементов, выбранных из исходного множества, содержащего $n$ различных видов объектов. При этом каждый объект может входить в состав комбинации несколько раз, а длина итогового набора $k$ может быть как меньше, так и значительно больше, чем число доступных видов $n$.
Главное отличие от обычных сочетаний заключается в том, что элементы после выбора не исключаются из исходного множества, а могут дублироваться. Например, если мы выбираем 3 буквы из набора «А, Б», то комбинация «ААА» или «АББ» является абсолютно допустимым сочетанием с повторениями.
Формула расчета числа сочетаний с повторениями
Прямого способа рассчитать такие комбинации нет, поэтому задачу всегда сводят к расчету обычных сочетаний без повторений, но с измененными параметрами. Число всех возможных сочетаний с повторениями обозначается символом $\bar{C}_n^k$ (буква $C$ с чертой наверху) и вычисляется по формуле:
$$\bar{C}_n^k = C_{n+k-1}^k = \frac{(n+k-1)!}{k! \cdot (n-1)!}$$
В этой формуле:
- $n$ — общее количество видов (типов) доступных объектов;
- $k$ — объем выборки, то есть количество объектов, которое необходимо выбрать.
Примеры решения задач
Разберем практические задачи, которые наглядно показывают работу этой формулы на примерах.
Задача 1 (Конфигурация ПК). Геймер собирает компьютер и заказывает в интернет-магазине 7 вентиляторов для корпуса. На складе в наличии есть вентиляторы четырех цветов: черные, белые, с синей подсветкой и с красной подсветкой. Сколькими способами можно сформировать этот заказ?
Порядок, в котором комплектующие будут лежать в коробке доставки, не имеет значения. Вентиляторы одного цвета абсолютно одинаковы и доступны в любом количестве, поэтому цвета в заказе могут повторяться (например, можно купить сразу 7 черных вентиляторов). Количество видов предметов $n = 4$, а объем нашей покупки $k = 7$. Подставим параметры в формулу:
$$\bar{C}_4^7 = C_{4+7-1}^7 = C_{10}^7 = \frac{10!}{7! \cdot (10-7)!} = $$$$ \frac{10 \cdot 9 \cdot 8}{1 \cdot 2 \cdot 3} = 120$$
Существует ровно 120 способов собрать такой комплект охлаждения.
Задача 2 (Жетоны в автомате). В автомате продаются памятные сувенирные жетоны с символикой трех видов: Космос, Наука и История. Пассажир опускает монеты и покупает любые 3 жетона. Сколько различных сувенирных наборов он может получить?
В этой задаче у нас есть $n = 3$ вида жетонов, а выбрать нужно $k = 3$ штуки. Так как жетоны одного дизайна одинаковы и в автомате их много, они могут повторяться в покупке. Порядок выдачи роли не играет, поэтому применим формулу:
$$\bar{C}_3^3 = C_{3+3-1}^3 = C_5^3 = \frac{5!}{3! \cdot (5-3)!} = $$$$ \frac{5 \cdot 4}{1 \cdot 2} = 10$$
Можно собрать ровно 10 вариантов тройки жетонов. Ниже наглядно представлены все возможные исходы этой выборки:
ККК
ККН
ККИ
КНН
КНИ
КИИ
ННН
ННИ
НИИ
ИИИ
Задача 3 (Рассылка писем). Курьер должен разнести 12 абсолютно одинаковых рекламных писем по 5 разным почтовым ящикам в подъезде. Сколькими способами он может распределить эти письма, если в каждый ящик можно положить любое количество (или не класть вовсе)?
Эта задача на распределение одинаковых объектов по разным адресатам. Представьте, что каждое опущенное письмо — это выбор конкретного почтового ящика. Нам нужно сделать $k = 12$ таких выборов (по числу писем), а выбирать мы можем из $n = 5$ доступных ящиков. Поскольку письма неотличимы друг от друга, их порядок внутри ящика роли не играет. Подставим данные в формулу:
$$\bar{C}_5^{12} = C_{5+12-1}^{12} = C_{16}^{12} = \frac{16!}{12! \cdot (16-12)!} = $$$$ \frac{16 \cdot 15 \cdot 14 \cdot 13}{1 \cdot 2 \cdot 3 \cdot 4} = 1820$$
Существует ровно 1820 уникальных способов разложить письма по ящикам.