Dudin ha scritto:Testo nascosto:I percorsi da contare sono:
percorsi totali - percorsi sbagliati.
Come si calcolano i percorsi totali?
Se il punto ha cordinate (a,b) ovviamente dovremo fare a mosse ad est e b mosse a nord.
Tuttavia la prima mossa è sempre a destra quindi ho fatto finta di partire non dall'origine ma dal punto (1,0) (si poteva fare anche dall'origine però)
Quindi le mosse totali diventano a-1 ad est e b a nord quindi:
[tex]\binom{a+b-1}{a-1}[/tex]
Come si calcolano i percorsi sbagliati?
Prendiamo il punto P' di coordinate (b-1,a).
I percorsi sbagliati sono quelli che partono dal punto (1,0) e arrivano a P' cioè
[tex]\binom{a+b-1}{a}[/tex]
Perche?
I percorsi sbagliati toccano il fiume arrivando in una coordinata compresa tra (1,2) e (b-1;b) (incluse) Infatti tutti i percorsi che vanno a P' toccano passano almeno in uno di quei punti.
Inoltre una volta toccato il punto oltre al fiume Bisogna aggiungere tutti i percorsi che vanno del punto oltre al fiume al punto di arrivo
(che sono le stesse che vanno dal punto oltre al fiume a P').
In altre parole tracciando una retta che passa per i punti subito dopo il fiume (0,1) (1,2) (2,2)... stiamo prendendo il simmetrico del punto di arrivo rispetto a quella retta.
ps non so se sono riuscito a spiegarmi bene ma puoi guardarti un video senior di combinatoria dove la cosa viene spiegata meglio
Si si ho capito il ragionamento.. È che non conoscendo la formula o la tipologia di questi problemi con una griglia ho avuto un sacco di difficoltà