Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

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

---

Формула

$\Huge{C_{n + k - 1}^{k} = \frac{{(n + k - 1)!}}{{k!(n - 1)!}}}$ Где:

• $n$ - общее количество элементов в множестве.
• $k$ - длина каждой комбинации.
• $n!$ - факториал числа n.
• $r!$ - факториал числа r.

Принцип работы

У нас есть набор из трёx элементов {A, B, C}. Мы хотим выбрать два элемента, причём каждый элемент может повторяться, и порядок не важен.

Определение переменных:

• $n$ — общее количество уникальных элементов, из которых мы выбираем. Здесь: $n=3$, так как у нас есть три элемента: A, B и C.
• $k$ — количество элементов, которые мы выбираем, причём каждый элемент может повторяться, а порядок не важен. В этом примере: $k=2$, так как нам нужно выбрать два элемента, но порядок не имеет значения.

Разберем все по шагам:

• Шаг 1: Подсчёт количества сочетаний с повторениями При сочетаниях с повторениями порядок не важен, но элементы могут повторяться. Формула для сочетаний с повторениями: $C_{n + k - 1}^{k} = \frac{{(n + k - 1)!}}{{k!(n - 1)!}}$

• Шаг 2: Подстановка значений Подставим значения $n=3$ и $k=2$ в формулу: $C_{3 + 2 - 1}^{2} = \frac{{(3 + 2 - 1)!}}{{2!(3 - 1)!}} = 6$ Это означает, что существует шесть уникальных способов выбрать два элемента из трёx, если каждый элемент может повторяться и порядок не имеет значения.

• Шаг 3: Проверка результата (перечисление сочетаний) Перечислим все возможные сочетания из двух букв, где порядок не важен и повторения разрешены: AA, AB, AC, BB, BC, CC.

Всего шесть уникальных сочетаний, что подтверждает правильность расчёта.

Вычислительная сложность

Вычислительная сложность $O(min⁡(k,n))$, так как при вычислении берется минимальное значение для оптимизации.

Пространственная сложность

Пространственная сложность $O(1)$, так как для хранения результата не требуется дополнительной памяти, связанной с $n$ или $k$.

---

Применение

Сочетания с повторениями имеют широкий спектр применений в различных областях:

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

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

3. Оптимизация. В оптимизационных задачах они могут использоваться для нахождения наилучших комбинаций параметров.

---

Готовые функции в Python

В Python, библиотека itertools предоставляет функции для работы с сочетаниями с повторениями, например:

• product(iterable, repeat) - Эта функция создает декартово произведение итерируемого объекта с самим собой $repeat$ раз. Это позволяет учитывать повторения элементов.
• combinations_with_replacement(iterable, r) - Эта функция генерирует сочетания длины $r$ с повторениями из итерируемого объекта. Она учитывает возможность повторения элементов в сочетаниях.

---

Готовые функции в C++

В C++, библиотека <algorithm> предоставляет функции для работы с сочетаниями с повторениями:

• next_permutation() - Эта функция предназначена для перестановок, но она также может быть адаптирована для создания сочетаний с повторениями.

---

Псевдокод

Функция СочетанияСПовторениями(сочетание, размер):
    n = ДлинаСписка(сочетание)

    Если размер < 0 или размер > n:
        Вернуть 0

    Результат = ВычислитьКоличествоСочетанийСПовторениями(n, размер)

    Вернуть Результат

---

Реализация на Python

Аннотация:
combinations_with_repetition - функция для вычисления количества сочетаний с повторениями
combination - последовательность элементов
size - размер сочетания
n - длина последовательности элементов
result - результат вычисления количества сочетаний с повторениями, основанный на формуле сочетаний с повторениями
combination - последовательность элементов, для которой вычисляется количество сочетаний с повторениями
size - размер сочетания
result - результат вычисления количества сочетаний с повторениями

import math

def combinations_with_repetition(combination, size):
    n = len(combination)

    if size < 0 or size > n:
        return 0

    result = math.comb(n + size - 1, size)
    
    return result

---

Олимпиадная реализация на С++

Аннотация:
comb_with_rep - функция для вычисления количества сочетаний с повторениями
fact - функция для вычисления факториала числа x
comb - заданное сочетание, представленное в виде вектора целых чисел
size - размер сочетания
n - длина последовательности элементов
res - результат вычисления количества сочетаний с повторениями, инициализируется единицей и затем умножается на n size раз

long long fact(int x) {
    long long res = 1;
    for (int i = 1; i <= x; i++) {
        res *= i;
    }
    return res;
}

long long comb_with_rep(const vector<int>& comb, int size) {
    int n = comb.size();

    if (size < 0 || size > n) {
        return 0;
    }
    long long res = (fact(n+size-1))/(fact(size)*fact(n-1));
    
    return res;
}

---

Продуктовая реализация на С++

Аннотация:
combinations_with_repetition - функция для вычисления количества сочетаний с повторениями
factorial - функция для вычисления факториала числа x
combination - ссылка на вектор элементов
size - размер сочетания
n - длина последовательности элементов
result - результат вычисления количества сочетаний с повторениями
combination - заданное сочетание, представленное в виде вектора целых чисел
size - размер сочетания
result - результат вычисления количества сочетаний с повторениями

#include <iostream>
#include <vector>
using namespace std;

long long factorial(int x) {
    long long result = 1;
    for (int i = 1; i <= x; i++) {
        result *= i;
    }
    return result;
}

long long combinations_with_repetition(const vector<int>& combination, int size) {
    int n = combination.size();

    if (size < 0 || size > n) {
        return 0;
    }
    long long result = (factorial(n+size-1))/(factorial(size)*factorial(n-1));
    
    return result;
}