Question

Использование рекуррентных соотношений Пусть 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

Answer 1

Ответ:

Пошаговое объяснение:

Для доказательства воспользуемся формулой числа сочетаний с повторениями $C_{n}^{k}=\frac{(n+k-1)!}{k!(n-1)!}$

$C_{n}^{0}=\frac{(n+0-1)!}{0!(n-1)!}=\frac{(n-1)!}{1*(n-1)!}=1$

$C_{n}^{1}=\frac{(n+1-1)!}{1!(n-1)!}=\frac{n!}{(n-1)!}=n$

$C_{n}^{m}=C_{n-1}^{m}+C_{n}^{m-1}\\\frac{(n+m-1)!}{m!(n-1)!}=\frac{(n-1+m-1)!}{m!(n-2)!}+\frac{(n+m-1-1)!}{(m-1)!(n-1)!}=\frac{(n+m-2)!*(n-1)+(n+m-2)!*m}{m!(n-1)!}$

$=\frac{(n+m-2)!*(n+m-1)}{m!(n-1)!}=\frac{(n+m-1)!}{m!(n-1)!}$

Answer 2

Для доказательства утверждения о рекуррентных соотношениях для числа сочетаний с повторениями давайте вначале определим, что такое f(n, m) - число сочетаний с повторениями из n по m.

Число сочетаний с повторениями из n по m обозначается как C(n, m) и представляет собой количество способов выбрать m элементов из набора из n элементов, где каждый элемент может быть выбран неограниченное количество раз.

Теперь давайте рассмотрим рекуррентные соотношения:

1. f(n, 0) = 1: Если m = 0, то у нас есть только один способ выбора элементов - не выбирать ни одного. Поэтому f(n, 0) = 1.

2. f(n, 1) = n: Если m = 1, то каждый из n элементов может быть выбран. Таким образом, f(n, 1) = n.

3. f(n, m) = f(n-1, m) + f(n, m-1) при 1 ≤ m ≤ n-1: Давайте рассмотрим выбор m элементов из набора из n элементов. Это можно сделать двумя способами: - Мы могли бы взять первый элемент и выбрать оставшиеся (m-1) элементов из того же набора, что и до этого. Это дает нам f(n, m-1) способов. - Мы могли бы не брать первый элемент и выбрать все m элементов из оставшихся (n-1) элементов. Это дает нам f(n-1, m) способов.

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

Таким образом, рекуррентные соотношения f(n, m) удовлетворяют условиям, описанным в вашем вопросе.