このバイナリ漸化式の式を見つけますか？ f（m、n）= f（m-1、n）+ f（m、n-1）

Question

SORRY GUYS！私の誤解！この問題は、グリッド（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がなければなりません。ちょうど1つの例：

RRUURURUUURUU 

この例では常に8個のUと5個のRがあります。異なる経路は異なる順序でそれらを持つだけです。だから私たちはUのために8つのポジションを選ぶことができ、残りはRでなければなりません。したがって、答えは

(8+5) choose (8) 

であるか、一般的には、

(m+n) choose (m) 

Answer 2

文献で「機能を生成する」を参照してください。 1つのアプローチは、x^m y^nの係数がf（m、n）である関数P（x、y）を想像することである。 P（x、y）-xP（x、y）=（1-xy）P（x、y）は、これらの厄介なものを除いてはかなりシンプルでなければならないエッジ値。次に、P（x、y）を解く。

あなたは確かにf(k,0) = f(0,k) = kで、1ではないでしょうか？もしあれば、私はいくつかの価値を書いて、彼らが何であるか推測し、それを証明するのが最善の策だと言いたいと思います。

Answer 3

これは単に、あなたは、彼らが同じ循環関係を満たすことを指摘することで、これを証明することができ、二項係数

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

です。

（ちょっと推測して確認できなかった場合）式を導出するには、Chris Nashが正しく示唆しているように生成関数を使用します。