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

Результат работы приведенного выше алгоритма:

Источник

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

Определение числа сочетаний

Пусть имеется $n$ различных объектов. Чтобы найти число сочетаний из $n$ объектов по $k$, будем выбирать комбинации из $m$ объектов все возможными способами, при этом будем обращать внимание на разный состав комбинаций, но не порядок (он тут не важен, в отличие от размещений).

Например, есть три объекта <1,2,3>, составляем сочетания по 2 объекта в каждом. Тогда выборки <1,2>и <2,1>— это одно и то же сочетание (так как комбинации отличаются лишь порядком). А всего различных сочетаний из 3 объектов по 2 будет три: <1,2>, <1,3>, <2,3>.

На картинке наглядно проиллюстрировано получение всех возможных сочетаний из 4 различных объектов по 2 (их будет 6, см. калькулятор сочетаний ниже, который даст формулу расчета).

Общая формула, которая позволяет найти число сочетаний из $n$ объектов по $k$ имеет вид:

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

Чтобы вычислить число сочетаний $C_n^k$ онлайн, используйте калькулятор ниже.

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

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

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

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

Решебник по ТВ

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Генерация сочетаний

В комбинаторике сочетанием из N различных элементов по M называется набор M элементов, выбранных из множества N элементов. Такие наборы отличаются только вхождением в них M определенных элементов, порядок следования элементов в таком наборе не важен. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, и этим сочетания отличаются от размещений.

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

Задача : Найти все возможные сочетания без повторений из множества элементов <1,2,3>по 2.
Существуют следующие сочетания:

1: 1 2
2: 1 3
3: 2 3

Количество возможных сочетаний без повторений из N элементов по M можно определить по формуле (N≥M):

что в M! раз меньше соответствующего количества размещений без повторений (поскольку сочетания без повторений не зависят от порядка следования элементов).

Рассмотрим задачу получения всех сочетаний для чисел 1…N по M.

Результат выполнения

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

Сочетаниями с повторениями называются наборы по M элементов, в которых каждый элемент множества N может участвовать несколько раз. При этом на соотношение значений M и N не накладывается никаких ограничений, а общее количество сочетаний с повторениями составляет

Примером такой задачи может служить выбор M открыток из N всеми возможными способами.

Для генерации сочетаний с повторениями воспользуемся решением для генерации размещений с повторениями, рассмотренным в этой статье.

Результат работы приведенного выше алгоритма:

Источник

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

Пусть имеются предметы n различных типов. Сколькими способами можно составить из них комбинацию из k элементов, если не принимать во внимание порядок элементов в комбинации, но при этом предметы одного и того же типа могут повторяться? Иными словами, различные комбинации должны отличаться количеством предметов хотя бы одного типа. Такие комбинации называются сочетаниями с повторениями.

Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Тогда из этих трёх элементов можно составить шесть сочетаний с повторениями по два элемента: ab, ac, bc, aa, bb, cc.

Таким образом, сочетание с повторениями из n элементов по k элементов (при этом допускается, что k>n) может содержать любой элемент сколько угодно раз от 1 до k включительно или не содержать его совсем, т.е. каждое сочетание с повторениями из n элементов по k элементов может состоять не только из k различных элементов, но и k каких угодно и как угодно повторяющихся элементов.

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

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

Данный онлайн калькулятор позволяет найти число сочетаний с повторениями из n элементов по k.

Онлайн калькуляторы

Calculatorium.ru — это бесплатные онлайн калькуляторы для самых разнообразных целей: математические калькуляторы, калькуляторы даты и времени, здоровья, финансов. Инструменты для работы с текстом. Конвертеры. Удобное решение различных задач — в учебе, работе, быту.

Актуальная информация

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

Источник

Генерация сочетаний из N элементов

Сочетания из N элементов по K в лексикографическом порядке

Постановка задачи. Даны натуральные числа N и K. Рассмотрим множество чисел от 1 до N. Требуется вывести все различные его подмножества мощности K, причём в лексикографическом порядке.

Алгоритм весьма прост. Первым сочетанием, очевидно, будет сочетание (1,2. K). Научимся для текущего сочетания находить лексикографически следующее. Для этого в текущем сочетании найдём самый правый элемент, не достигший ещё своего наибольшего значения; тогда увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения.

С точки зрения производительности, этот алгоритм линеен (в среднем), если K не близко к N (т.е. если не выполняется, что K = N — o(N)). Для этого достаточно доказать, что сравнения «a[i] k раз, т.е. в (N+1) / (N-K+1) раз больше, чем всего есть сочетаний из N элементов по K.

Сочетания из N элементов по K с изменениями ровно одного элемента

Требуется выписать все сочетания из N элементов по K, но в таком порядке, что любые два соседних сочетания будут отличаться ровно одним элементом.

Интуитивно можно сразу заметить, что эта задача похожа на задачу генерации всех подмножеств данного множества в таком порядке, когда два соседних подмножества отличаются ровно одним элементом. Эта задача непосредственно решается с помощью Кода Грея: если мы каждому подмножеству поставим в соответствие битовую маску, то, генерируя с помощью кодов Грея эти битовые маски, мы и получим ответ.

Может показаться удивительным, но задача генерации сочетаний также непосредственно решается с помощью кода Грея. А именно, сгенерируем коды Грея для чисел от 0 до 2 N -1, и оставим только те коды, которые содержат ровно K единиц. Удивительный факт заключается в том, что в полученной последовательности любые две соседние маски (а также первая и последняя маски) будут отличаться ровно двумя битами, что нам как раз и требуется.

Для доказательства вспомним факт, что последовательность G(N) кодов Грея можно получить следующим образом:

т.е. берём последовательность кодов Грея для N-1, дописываем в начало каждой маски 0, добавляем к ответу; затем снова берём последовательность кодов Грея для N-1, инвертируем её, дописываем в начало каждой маски 1 и добавляем к ответу.

Теперь мы можем произвести доказательство.

Сначала докажем, что первая и последняя маски будут отличаться ровно в двух битах. Для этого достаточно заметить, что первая маска будет иметь вид N-K нулей и K единиц, а последняя маска будет иметь вид: единица, потом N-K-1 нулей, потом K-1 единица. Доказать это легко по индукции по N, пользуясь приведённой выше формулой для последовательности кодов Грея.

Теперь докажем, что любые два соседних кода будут отличаться ровно в двух битах. Для этого снова обратимся к формуле для последовательности кодов Грея. Пусть внутри каждой из половинок (образованных из G(N-1)) утверждение верно, докажем, что оно верно для всей последовательности. Для этого достаточно доказать, что оно верно в месте «склеивания» двух половинок G(N-1), а это легко показать, основываясь на том, что мы знаем первый и последний элементы этих половинок.

Приведём теперь наивную реализацию, работающую за 2 N :

Стоит заметить, что возможна и в некотором смысле более эффективная реализация, которая будет строить всевозможные сочетания на ходу, и тем самым работать за O (C_n k n). С другой стороны, эта реализация представляет собой рекурсивную функцию, и поэтому для небольших n, вероятно, она имеет большую скрытую константу, чем предыдущее решение.

Собственно сама реализация — это непосредственное следование формуле:

Эта формула легко получается из приведённой выше формулы для последовательности Грея — мы просто выбираем подпоследовательность из подходящих нам элементов.

Источник