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)!}$