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

ИСТОРИЧЕСКИЕ ПАРКИ! ВИНОВАТ! Спасибо за ваше напоминание, я узнал 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

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

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

Ответы

Ответ 1

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

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

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

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

RRUURURUUURUU

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

(8+5) choose (8)

Или, вообще говоря,

(m+n) choose (m)

Ответ 2

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

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

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

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

Ответ 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, может быть? Если бы это было так, я бы сказал, что лучше всего было бы написать некоторые значения, угадать, что они есть, а затем доказать это.