Использование рекуррентных соотношений Пусть f(n.m) – число сочетаний с повторениями из n по m.
Проверьте, что
f(n.0) = 1, f(n.1) = n, f(n.m) = f(n-1.m) + f(n.m-1) при 1 ≤ m ≤ n - 1

Предыдущий
вопрос Следующий
вопрос

Докажем данное утверждение математически:

Базовые случаи:

f(n, 0) = 1, так как при m = 0 у нас нет элементов, из которых нужно выбирать сочетания, поэтому единственное возможное сочетание – это пустое множество.f(n, 1) = n, так как при m = 1 мы должны выбрать по одному элементу из n, что можно сделать n способами.

Шаг индукции:
Для доказательства рекуррентного соотношения f(n, m) = f(n-1, m) + f(n, m-1) воспользуемся принципом индукции.

Предположение индукции: Пусть утверждение верно для всех k, где 1 ≤ k < n.

Теперь рассмотрим случай m = 1:
f(n, 1) = n = f(n-1, 1) + f(n, 0) = f(n-1, 1) + 1. Утверждение верно в случае m = 1.

Предположим, что утверждение верно для m, и покажем, что оно верно и для m+1:
f(n, m+1) = f(n-1, m+1) + f(n, m)
f(n, m+1) = f(n-1, m) + f(n, m) = f(n, m) + f(n, m) = 2f(n, m) = 2[f(n-1, m) + f(n, m-1)] = 2f(n-1, m) + 2f(n, m-1)

Таким образом получаем, что f(n, m+1) = 2f(n-1, m) + 2f(n, m-1), что также соответствует рекуррентному соотношению.

Таким образом, мы доказали, что утверждение верно для всех n и m.