7.1.2. Комбинации с повторениями

Определения и обозначения

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

Число сочетаний с повторениями — количество различных способов выбрать k предметов из n видов. Его обозначают C̄(n, k), а вычисляют по формуле C(n+k−1, k). Формула нужна, чтобы быстро получить число вариантов, когда повторения разрешены.

В записи используются два параметра: n — количество видов предметов, а k — количество выбираемых предметов. Оба числа являются целыми неотрицательными числами. Сначала определяют эти параметры по условию, а затем подставляют их в формулу.

Как это устроено

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

Чтобы свести задачу к сочетанию без повторений, представим выбранные предметы группами по видам. Группы разделим перегородками: первая группа относится к первому виду, вторая — ко второму и так далее. Например, запись ●●|●|| означает два предмета первого вида, один второго и ни одного третьего.

В такой записи находятся k обозначений предметов и n−1 разделителей. Значит, всего имеется k+n−1 мест. Достаточно выбрать, какие k мест займут обозначения предметов, потому что остальные места автоматически станут разделителями; поэтому получается C(n+k−1, k).

Формула допускает многократный выбор одного вида: несколько обозначений могут стоять подряд между соседними разделителями. Если все k обозначений находятся в одной группе, это означает выбор всех предметов одного вида. Если между двумя разделителями ничего нет, соответствующий вид не выбран.

Для решения задачи сначала находят число видов n и общее число выбираемых предметов k. Затем подставляют их в C(n+k−1, k) и вычисляют биномиальный коэффициент, то есть число сочетаний без повторений из указанного количества элементов. Последний шаг — проверить, что порядок действительно не важен и повторения разрешены.

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

Таблица показывает главное различие между двумя моделями: порядок в обеих не важен, но повторения разрешены только во второй. Перед вычислением нужно определить, можно ли выбрать несколько предметов одного вида. Если можно, используют правый столбец и формулу C(n+k−1, k).

Разбор задач

Выбор конфет

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

1. Число видов конфет: n = 3.
2. Число выбираемых конфет: k = 2.
3. Подставляем значения: C(3+2−1, 2) = C(4, 2).
4. Вычисляем: C(4, 2) = 6.

Ответ: 6 разных выборов. Среди них есть варианты с двумя конфетами одного вида, поэтому формула без повторений дала бы неполный результат.

Шарики разных цветов

Нужно выбрать три шарика из четырёх цветов, причём шарики одного цвета неразличимы, а цвета могут повторяться. Поэтому выбор определяется только количеством шариков каждого цвета. Это сочетание с повторениями, где n = 4 и k = 3.

1. Записываем параметры: n = 4, k = 3.
2. Используем формулу: C(n+k−1, k) = C(4+3−1, 3) = C(6, 3).
3. Вычисляем биномиальный коэффициент: C(6, 3) = 20.

Ответ: 20 способов. Например, можно взять три шарика одного цвета, по одному трёх цветов или два одного цвета и один другого; все такие составы учитываются.

Распределение конфет по коробкам

Пять одинаковых конфет раскладывают по трём коробкам, и коробка может быть пустой. Пусть x₁, x₂ и x₃ — количества конфет в коробках, тогда x₁ + x₂ + x₃ = 5, а каждое число неотрицательно. Это равносильно выбору пяти одинаковых предметов из трёх видов, где вид означает коробку.

1. Число групп, или коробок: n = 3.
2. Число одинаковых предметов: k = 5.
3. Применяем формулу: C(3+5−1, 5) = C(7, 5).
4. Получаем: C(7, 5) = 21.

Ответ: 21 способ. Пустая коробка учитывается благодаря возможности оставить одну или несколько групп без предметов.

Типичные ошибки

Учитывать порядок выбора. Так один и тот же набор записывают несколько раз: сначала взяли яблоко, потом грушу или наоборот. Проверьте, меняется ли состав набора при перестановке действий; если нет, порядок учитывать нельзя.

Использовать C(n, k). Эта формула относится к выбору без повторений и не разрешает взять несколько предметов одного вида. Спросите себя, может ли один вид встретиться дважды; при положительном ответе нужна формула C(n+k−1, k).

Перепутать n и k. Число видов — это n, а количество выбранных предметов — k, даже если предметы распределяют по коробкам. Полезно подписать параметры словами до подстановки.

Забыть −1 в выражении n+k−1. Разделителей между n группами ровно n−1, поэтому подстановка n+k или n−k неверна. Перед вычислением пересчитайте: k обозначений предметов плюс n−1 разделителей.

Связь с другими темами

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

Что запомнить

• В сочетаниях с повторениями порядок выбора не важен.
• Предметы одного вида можно выбирать несколько раз.
• n — число видов, k — число выбираемых предметов.
• Число сочетаний с повторениями равно C(n+k−1, k).
• При распределении одинаковых предметов по группам число групп соответствует числу видов.
• Пустая группа допускается, если условие разрешает не выбирать предметы этого вида.