"Алгебра и начала математического анализа", Колягин Ю.М., Ткачёва М.В. и др.
Сочетания с повторениями помогают посчитать наборы, в которых порядок выбора не важен, а элементы одного вида разрешено брать несколько раз. Например, так можно определить, сколькими способами выбрать несколько конфет из разных видов. Выбор описывают количеством элементов каждого вида, а затем используют формулу C(n + k − 1, k). Её смысл раскрывает метод шаров и перегородок — модель распределения одинаковых объектов по группам.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Сочетание с повторениями — выбор нескольких элементов из набора, при котором порядок не учитывается, а элементы одного вида могут выбираться неоднократно. Например, набор из двух яблок и одной груши не меняется, если перечислить его в другом порядке. Такое понятие нужно, когда считаются составы наборов, а не последовательности выбора.
Число сочетаний с повторениями — количество различных наборов из k элементов, составленных из n видов с разрешёнными повторами. Два набора считаются различными, если в них отличается количество элементов хотя бы одного вида. Это число позволяет сразу подсчитать все возможные составы, не перечисляя их по одному.
Сочетания с повторениями обозначают C̅ₙᵏ; также встречается запись C(n + k − 1, k). Нижний индекс n указывает число доступных видов элементов, а верхний индекс k — сколько элементов всего нужно выбрать. Такое обозначение напоминает обычное число сочетаний, но черта показывает, что повторения разрешены.
Метод шаров и перегородок — способ представить выбор как распределение одинаковых объектов по группам. Шары обозначают выбранные элементы, перегородки разделяют их по видам. Модель нужна, чтобы обосновать формулу подсчёта и связать сочетания с повторениями с уравнениями в неотрицательных целых числах.
У сочетаний без повторений и с повторениями одинаковое главное свойство: перестановка выбранных элементов не создаёт новый вариант. Различие состоит в допустимости повторов: без повторений каждый вид можно взять не более одного раза, а с повторениями — несколько раз. Поэтому обычная формула C(n, k) не подходит для повторного выбора: она считает наборы из разных элементов. В задачах сначала выясняют, что именно считается и разрешено ли брать один вид снова.
Чтобы описать любой набор, обозначим через xᵢ число элементов i-го вида. Например, x₁ — количество предметов первого вида, x₂ — второго, и так далее. Все xᵢ являются неотрицательными целыми числами, потому что количество предметов не бывает отрицательным или дробным. Если выбрано всего k элементов, то x₁ + x₂ + … + xₙ = k; каждому набору соответствует ровно одно решение этого уравнения.
Уравнение можно представить наглядно: k одинаковых шаров распределяют между n группами, а пустая группа означает, что элемент соответствующего вида не выбран. Чтобы получить группы в одной строке, ставят между ними n − 1 перегородок. Например, несколько перегородок подряд означают пустую группу, а шары до первой перегородки показывают количество элементов первого вида. Такое представление работает и тогда, когда в отдельной группе нет ни одного шара.
Всего в строке находятся k шаров и n − 1 перегородок, то есть n + k − 1 позиций. Достаточно выбрать k позиций для шаров, а оставшиеся отдать перегородкам; поэтому число распределений равно C(n + k − 1, k). Можно вместо этого выбрать n − 1 мест для перегородок, получая равную запись C(n + k − 1, n − 1). Так возникает формула C̅ₙᵏ = C(n + k − 1, k), а не просто правило, которое нужно заучить.
Дополнительное условие меняет задачу, поэтому сначала его нужно перевести в действие с наборами. Если один предмет обязателен, можно заранее взять его и распределить оставшееся количество. Если требуется исключить наборы без предмета заданного вида, считают все варианты, затем отдельно — варианты без этого вида, и вычитают их. Вычитание удобно, когда запрещённые варианты проще подсчитать, чем наборы, удовлетворяющие условию.
| Характеристика | Сочетания без повторений | Сочетания с повторениями |
|---|---|---|
| Учитывается ли порядок элементов | Нет | Нет |
| Может ли один вид элемента повторяться | Нет | Да |
| Обозначение | Cₙᵏ | C̅ₙᵏ |
| Формула числа сочетаний | C(n, k) | C(n + k − 1, k) |
| Модель через распределение элементов | Выбор разных элементов из n | k одинаковых объектов по n группам |
| Допустимые значения n и k | n ≥ 0, 0 ≤ k ≤ n | n ≥ 1, k ≥ 0 |
Сначала проверьте, важен ли порядок: в обеих колонках он не учитывается. Затем уточните, разрешено ли повторять вид элемента, и выберите соответствующую формулу. Обратите внимание, что при повторениях k может быть больше n.
Сколькими способами можно выбрать 3 конфеты из 5 видов, если конфеты одного вида можно брать несколько раз? Порядок, в котором кладут конфеты в коробку, не меняет её состав. Поэтому нужно считать сочетания с повторениями, где n = 5, а k = 3. Используем формулу C(n + k − 1, k).
Получилось 35 составов коробки. Например, конфеты могут быть все одного вида или распределиться между несколькими видами. Ответ: 35 способов.
Сколько существует неотрицательных целочисленных решений уравнения x₁ + x₂ + x₃ + x₄ = 6? Каждая переменная показывает, сколько шаров попало в одну из четырёх групп. Поэтому задача равносильна распределению 6 одинаковых шаров по 4 группам. Нулевое значение переменной допустимо и означает пустую группу.
Каждое распределение задаёт ровно один набор значений переменных, и наоборот. Значит, уравнение имеет 84 неотрицательных целочисленных решения. Ответ: 84 решения.
Сколькими способами можно выбрать 5 предметов из 7 видов, если предмет заданного вида должен присутствовать хотя бы один раз? Сначала подсчитаем все наборы, не накладывая условие, а затем исключим наборы без нужного вида. Для общего числа берём n = 7 и k = 5. В исключаемых наборах остаются только 6 видов, из которых нужно выбрать все 5 предметов.
Вычитание оставляет только наборы, в которых заданный вид встречается хотя бы один раз. Это работает потому, что каждый набор либо содержит этот вид, либо не содержит его. Ответ: 210 способов.
Используют C(n, k), забывая, что повторы разрешены. Так поступают, когда ориентируются только на слова «выбрать k из n» и не проверяют условия. Формула без повторений может дать слишком маленький результат или даже ноль, если k больше n. Проверьте себя: допускает ли задача два предмета одного вида?
Учитывают порядок выбора, хотя важен только состав набора. Обычно это происходит, когда элементы мысленно перечисляют по очереди и считают разные последовательности. Чтобы проверить подсчёт, сравните два варианта, отличающихся только порядком: если набор тот же, это не два сочетания. Для порядка применяют другие комбинаторные модели.
В формуле вместо n + k − 1 используют n + k или n + k − 2. Ошибка возникает при подсчёте перегородок: между n группами нужно ровно n − 1 разделитель. Проверьте сумму: k шаров плюс n − 1 перегородка дают n + k − 1 позиций. При n = 1 перегородок нет, что также подтверждает формулу.
Путают число видов n с количеством выбранных элементов k. Тогда в формулу подставляют не те значения и получают неверный ответ. Перед вычислением подпишите параметры: n отвечает на вопрос «сколько видов доступно?», а k — «сколько всего выбираем?». Проверьте, что при изменении числа предметов меняется k, а при добавлении нового вида — n.
Для сочетаний с повторениями нужны сочетания без повторений, биномиальные коэффициенты и понимание выбора без учёта порядка. Метод шаров и перегородок связывает комбинаторику с уравнениями, имеющими неотрицательные целочисленные решения. Та же модель помогает считать распределения одинаковых предметов, наборы товаров и ресурсы. В более широком смысле такие подсчёты встречаются в комбинаторике и теории вероятностей.
В сочетаниях с повторениями порядок выбранных элементов не учитывается.
Один и тот же вид элемента можно выбирать несколько раз.
Выбор k элементов из n видов описывается уравнением x₁ + … + xₙ = k.
Число сочетаний с повторениями равно C(n + k − 1, k).
Метод шаров и перегородок объясняет происхождение формулы.
При дополнительных ограничениях нужно фиксировать обязательные элементы или исключать запрещённые варианты.
Чем сочетания с повторениями отличаются от сочетаний без повторений?
В обоих случаях порядок элементов не учитывается. Но в сочетаниях с повторениями один и тот же вид можно выбрать несколько раз, а без повторений каждый элемент выбирают не более одного раза.
Почему в формуле появляется число n + k − 1?
Чтобы распределить k одинаковых объектов по n группам, изображают k шаров и n − 1 перегородок. Вместе получается n + k − 1 позиций, а выбор мест для шаров или перегородок задаёт распределение.
Как понять, учитывать ли порядок элементов в задаче?
Спросите себя, изменится ли результат, если те же элементы расположить иначе. Если набор остаётся тем же, порядок не важен; если меняются роли или последовательность, перед вами другой тип подсчёта.
Можно ли использовать формулу сочетаний с повторениями, если некоторые элементы обязательны?
Можно, если сначала учесть обязательные элементы. Например, один обязательный элемент фиксируют, а для остальных считают сочетания с повторениями; также можно посчитать все наборы и вычесть те, где условие нарушено.
Как связаны сочетания с повторениями и решения уравнения x₁ + … + xₙ = k?
Каждое решение уравнения задаёт, сколько раз выбран элемент каждого из n видов. Числа x₁, …, xₙ неотрицательны, а их сумма равна k, поэтому решения соответствуют распределениям k одинаковых объектов по n группам.
§ 6. Сочетания с повторениями
