Сполучення з необмеженими повтореннями

Будемо розглядати к- сполучення з елементів множини М

,

Тобто кратність будь-якого елемента в сполученні можуть бути від 0 до к. Для зручності позначимо всі елементи множини М₁ через 1, М₂ через 2, М_n – n.

Число всіх різних сполучень із елементів n – типів по k при заданих обмеженнях позначено

Візьмемо довільне k– сполучення {a₁, a₂, …, a_n}, упорядкуємо елементи сполучення, так щоб 1 ≤ a₁ ≤ a₂ ≤ …≤ a_k ≤ n. Введемо допоміжну підмножину В, що складається з {1,2,3,…,n+k-1}

Поставимо у відповідності k-сполучення з необмеженими повтореннями k- сполучення. без повторень із елементів множини В за таким правилом:

{ a₁, a₂ + 1, a₃ + 2, …, a_k + k-1}

Проробимо цю же операцію з кожним k-сполученням.

При цьому встановиться взаємно однозначна відповідність між k- сполученнями з необмеженими повтореннями з М и k-сполученнями без повторень із множини В. Тоді:

(2)

Тема 4. Теорія графів