Найти формулу этого бинарного рекуррентного уравнения?f (m, n) = f (m-1, n) + f (m, n-1)

Question

Извините, ребята! ВИНОВАТ! Спасибо за ваше напоминание, я узнал, f (0, k) == f (k, 0) == 1. Этот вопрос о том, как подсчитать количество кратчайших путей от сетки (0,0) до (m, n ).

Теперь я должен решить следующее уравнение, чтобы точно выяснить, что f (m, n) равно.

1) f(m,n) = 0 : when (m,n) = (0,0)
**2) f(m,n) = 1 : when f(0,k) or f(k,0)**
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else

например:

1) f(0,0) = 0; 
2) f(0,1) = 1; f(2,0) = 1; 
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3  

Я помню, что существует стандартный способ решения такого рода бинарного рекуррентного уравнения, который я выучил в классе алгоритмов несколько лет назад, но сейчас я просто не могу вспомнить.

Может ли кто-нибудь дать намек? Или ключевое слово как найти ответ?

Answer 1

Тьфу, мне было просто весело просматривать мои старые учебники по генерации функций, а вы пошли и снова изменили вопрос!

Этот вопрос о том, как посчитать количество кратчайших путей от сетки (0,0) до (m, n).

Это основной вопрос комбинаторики - он не требует знания ничего о генерации функций или даже о рекуррентных отношениях.

Чтобы решить, представьте, что пути записываются в виде последовательности U (для «вверх») и R (для «вправо»). Если мы переходим от (0,0) к, скажем, (5, 8), должно быть 5 R и 8 U. Только один пример:

RRUURURUUURUU

В этом примере всегда будет 8 U и 5 R; разные пути будут просто иметь их в разных порядках. Таким образом, мы можем просто выбрать 8 позиций для наших U, а остальные должны быть R. Таким образом, ответ

(8+5) choose (8)

Или вообще

(m+n) choose (m)

Answer 2

Это просто биномиальный коэффициент

f(m,n) = (m+n choose m) = (m+n choose n)

Вы можете доказать это, отметив, что они удовлетворяют одному и тому же соотношению повторения.

Чтобы вывести формулу (если вы не могли просто догадатьсяи затем проверьте), используйте генерирующие функции, как правильно предлагает Крис Нэш.

Answer 3

Попробуйте поискать «производящие функции» в литературе. Один из подходов состоит в том, чтобы представить функцию P (x, y), где коэффициент x ^ m y ^ n равен f (m, n). Линия повторения (строка 3) говорит вам, что P (x, y) - xP (x, y) - yP (x, y) = (1-xy) P (x, y) должно быть довольно простым, за исключением тех надоедливых граничные значения. Тогда решите для P (x, y).

Вы уверены f(k,0) = f(0,k) = k, а не 1, может быть? Если бы это было так, я бы сказал, что лучше всего было бы выписать некоторые значения, угадать, что они есть, а затем доказать это.