Trova la formula di questa equazione di ricorrenza binaria? f (m, n) = f (m-1, n) + f (m, n-1)

Question

SORRY GUYS! ERRORE MIO! Grazie per il tuo promemoria, ho scoperto f (0, k) == f (k, 0) == 1. Questa domanda riguarda come contare il numero di percorsi più brevi dalla griglia (0,0) a (m, n).

Devo risolvere la seguente equazione ora, scoprire esattamente che f (m, n) è uguale a.

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 

ad esempio:

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 

Mi ricordo che è un modo standard per risolvere tali tipi di equazione recidiva binario come ho imparato nella mia classe algoritmo di diversi anni fa, ma non riesco proprio a ricordare per ora .

Qualcuno può dare qualche suggerimento? O una parola chiave come trovare la risposta?

Answer 1

Ugh, mi stavo solo divertendo a passare attraverso i miei vecchi libri di testo sulla generazione di funzioni, e sei andato a cambiare di nuovo la domanda!

Questa domanda riguarda come contare il numero del percorso più breve dalla griglia (0,0) a (m, n).

Questa è una domanda combinatoria di base: non richiede di sapere nulla sulla generazione di funzioni o anche sulle relazioni di ricorrenza.

Per risolvere, immaginare i percorsi che vengono scritti come una sequenza di U (per "su") e R (per "destra"). Se ci spostiamo da (0,0) a, per esempio, (5, 8), ci devono essere 5 R e 8 U. Un solo esempio:

RRUURURUUURUU 

Ci saranno sempre, in questo esempio, 8 U e 5 R; percorsi diversi li avranno solo in diversi ordini. Quindi possiamo solo scegliere 8 posizioni per le nostre U, e il resto deve essere R. Quindi, la risposta è

(8+5) choose (8) 

o, in generale,

(m+n) choose (m) 

Answer 2

Prova a cercare "funzioni generatrici" nella letteratura. Un approccio sarebbe immaginare una funzione P (x, y) in cui il coefficiente di x^m y^n è f (m, n). La linea di ricorrenza (riga 3) ti dice che P (x, y) - xP (x, y) - yP (x, y) = (1-xy) P (x, y) dovrebbe essere piuttosto semplice ad eccezione di quelli fastidiosi valori del bordo. Quindi risolvere per P (x, y).

Sei sicuro di f(k,0) = f(0,k) = k e non 1, forse? Se lo fosse, direi che la soluzione migliore sarebbe scrivere alcuni valori, indovinare cosa sono, quindi dimostrarlo.

Answer 3

Questo è semplicemente il coefficiente binomiale

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

È possibile dimostrare questo notando che soddisfino la stessa relazione ricorrente.

Per ricavare la formula (se non si è in grado di indovinare e quindi verificare), utilizzare le funzioni di generazione come suggerisce correttamente Chris Nash.