"Алгебра и начала математического анализа. Углубленный уровень", Виленкин Н.Я., Ивашев-Мусатов О.С., Шварцбурд С.И.
Сочетания с повторениями помогают считать выборы, в которых предметы одного вида разрешено брать несколько раз, а порядок не имеет значения. Например, так можно посчитать наборы пирожных разных видов или распределения одинаковых жетонов по коробкам. Число таких выборов из n видов по k предметов равно C̄ₙᵏ = Cₙ₊ₖ₋₁ᵏ. Формула связана с решениями уравнения x₁ + … + xₙ = k в неотрицательных целых числах.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Сочетание с повторениями — это выбор нескольких предметов из нескольких видов, при котором один и тот же вид можно взять несколько раз, а порядок выбора не важен. Например, набор из двух пирожных одного вида допустим, даже если в кондитерской есть и другие виды. Такое определение подходит, когда нас интересует состав набора, а не последовательность действий при покупке. Оно помогает сразу отличить эту задачу от выбора предметов без повторений.
Число сочетаний с повторениями из n видов по k предметов обозначают C̄ₙᵏ. Здесь n — количество видов, из которых выбирают, а k — общее количество выбираемых предметов. Черта над C напоминает, что допускаются повторения; это отличает обозначение от обычного числа сочетаний Cₙᵏ. Уточнение n и k не даёт перепутать число доступных видов с размером набора.
Каждый выбор можно описать числами x₁, …, xₙ, где xᵢ показывает, сколько предметов взято из i-го вида. Эти числа неотрицательны: вид можно не выбрать, поэтому допускается xᵢ = 0. Их сумма равна k, то есть x₁ + … + xₙ = k. Такая запись превращает задачу о наборах в задачу о подсчёте решений уравнения.
В обычных сочетаниях предмет одного вида нельзя взять повторно, а в сочетаниях с повторениями это разрешено. Поэтому в наборе могут быть, например, два пирожных одного вида. Однако перестановка предметов не создаёт нового выбора: набор из пирожных одного и другого вида остаётся тем же независимо от порядка, в котором их положили в коробку. Значит, считать нужно состав набора, а не способы его упорядочить.
Представим виды как группы, а число предметов каждого вида обозначим x₁, …, xₙ. Всего выбрано k предметов, поэтому суммы количеств достаточно, чтобы полностью описать выбор: x₁ + … + xₙ = k. Каждое xᵢ должно быть целым и неотрицательным, поскольку нельзя выбрать дробную часть предмета или отрицательное число предметов. И наоборот, любое решение этого уравнения задаёт ровно один состав набора.
Чтобы посчитать такие решения, изобразим каждый выбранный предмет звёздочкой, а виды разделим перегородками. Например, звёзды между первой и второй перегородками соответствуют предметам первого вида. Для n групп достаточно n − 1 перегородки, потому что границы групп образуются именно между соседними видами. Перегородки могут стоять рядом или у края: так обозначаются группы, в которых нет предметов.
После такой записи нужно расположить вместе k звёздочек и n − 1 перегородку. Всего имеется k + n − 1 мест, и достаточно выбрать, какие из них займут звёздочки: остальные будут перегородками. Поэтому число выборов равно Cₙ₊ₖ₋₁ᵏ; если выбрать места для перегородок, получится равное выражение Cₙ₊ₖ₋₁ⁿ⁻¹. Итак, C̄ₙᵏ = Cₙ₊ₖ₋₁ᵏ = Cₙ₊ₖ₋₁ⁿ⁻¹.
Формула применима, когда n — положительное целое число видов, а k — неотрицательное целое число предметов. При k = 0 выбирать нечего, и возможен ровно один пустой набор; формула даёт Cₙ₋₁⁰ = 1. При n = 1 все k предметов относятся к единственному виду, поэтому выбор также один: C̄₁ᵏ = Cₖᵏ = 1. Эти крайние случаи помогают проверить, что обозначения и формула используются правильно.
| Что сравниваем | Без повторений | С повторениями |
|---|---|---|
| Можно ли выбирать предметы одного вида несколько раз | Нет, каждый предмет выбирают не более одного раза | Да, вид можно выбрать повторно |
| Условие на число выбираемых предметов | 0 ≤ k ≤ n | k ≥ 0, n ≥ 1 |
| Формула числа выборов из n видов по k предметов | Cₙᵏ | C̄ₙᵏ = Cₙ₊ₖ₋₁ᵏ |
| Когда порядок выбора не учитывается | Всегда: важен только набор разных предметов | Всегда: важны количества предметов каждого вида |
| Модель через количества предметов каждого вида | xᵢ = 0 или 1, сумма xᵢ равна k | xᵢ ≥ 0, сумма xᵢ равна k |
Сначала выясните, разрешено ли выбирать один вид несколько раз: это определяет, какой формулой пользоваться. Затем проверьте, что порядок действительно не создаёт новых вариантов. Модель с количествами особенно удобна, если предметы одинаковы, а виды или группы различимы.
Задача 1. Сколькими способами можно выбрать 2 пирожных из 4 видов, если пирожные одного вида могут повторяться? Порядок покупки не меняет набор: два пирожных одного вида — такой же выбор независимо от того, какое положили первым. Поэтому здесь нужны сочетания с повторениями, где n = 4, а k = 2.
Задача 2. Сколькими способами можно купить 6 одинаковых яблок, выбирая их из 3 сортов? Обозначим через x₁, x₂ и x₃ количество яблок каждого сорта. Условие покупки записывается как x₁ + x₂ + x₃ = 6, где все xᵢ — неотрицательные целые числа.
Задача 3. Сколькими способами можно распределить 10 одинаковых жетонов по 4 коробкам, если коробка может быть пустой? Коробки различимы, а жетоны одинаковы, поэтому важны только количества жетонов в каждой коробке. Это те же неотрицательные решения уравнения x₁ + x₂ + x₃ + x₄ = 10.
Используют формулу обычных сочетаний Cₙᵏ, хотя предметы одного вида разрешено выбирать повторно. Так происходит, если ориентироваться только на слова «выбрать k из n» и не проверить условия. Перепишите выбор как количества xᵢ: если они могут быть больше 1, нужна формула сочетаний с повторениями.
Считают разные порядки выбора разными вариантами, например записывают покупку «груша, яблоко» отдельно от «яблоко, груша». Ошибка появляется, когда выбор путают с последовательностью действий. Проверьте, изменился ли состав набора: если нет, то нового сочетания нет.
Ставят n перегородок вместо n − 1 в методе звёзд и перегородок. Причина — представление, будто каждой группе нужна отдельная перегородка, хотя крайние границы уже задаются краями записи. Для n групп оставьте только промежутки между ними и проверьте: при одном виде перегородок быть не должно.
Не допускают пустые группы и исключают выборы, где некоторый вид не представлен. Обычно забывают, что неотрицательное количество может быть нулём. В модели звёзд и перегородок пустая группа видна по двум соседним перегородкам или перегородке у края; убедитесь, что такие расположения разрешены условием.
Для работы с формулой полезны обычные сочетания и биномиальные коэффициенты, а также умение отличать выбор с учётом порядка от выбора без него. Представление через уравнение с неотрицательными целыми решениями применяется в задачах о распределении одинаковых предметов по группам. Этот же приём встречается при подсчёте одночленов заданной степени: показатели переменных играют роль количеств предметов. Поэтому сочетания с повторениями связывают комбинаторику с алгебраическими задачами и моделями распределения ресурсов.
Чем сочетание с повторениями отличается от обычного сочетания?
В обычном сочетании каждый предмет можно выбрать не более одного раза. В сочетании с повторениями один и тот же вид допускается выбирать несколько раз, но порядок выбранных предметов по-прежнему не учитывается.
Почему в формуле появляется число n + k − 1?
Чтобы разделить k одинаковых отметок на n групп, нужно поставить между группами n − 1 перегородку. Всего получается k + n − 1 позиций, из которых выбирают k позиций для отметок или n − 1 для перегородок.
Почему порядок выбранных предметов не влияет на число сочетаний?
Сочетание описывает только состав набора, а не последовательность, в которой его набрали. Например, выбор яблока и груши одинаков и при порядке «яблоко, груша», и при порядке «груша, яблоко».
Можно ли не выбирать предметы какого-либо вида?
Да. Количество предметов каждого вида может быть равно нулю, поэтому в записи через звёзды и перегородки допустимы пустые группы.
Как понять, что задачу о распределении можно решить сочетаниями с повторениями?
Проверьте, одинаковы ли распределяемые предметы и различаются ли группы или виды, куда их кладут. Если предметы одинаковы, группы различимы, а группа может получить любое неотрицательное количество предметов, задача сводится к сочетаниям с повторениями.
7. Сочетания с повторениями
