Percorsi minimi su una griglia

Testo

Su una griglia rettangolare, si vuole andare dal vertice in alto a sinistra $A$ a quello in basso a destra $B$, muovendosi lungo le linee e a ogni passo spostandosi di una unità verso destra oppure di una unità verso il basso. Se per arrivare in $B$ occorrono $5$ passi verso destra e $3$ passi verso il basso, quanti percorsi minimi diversi esistono?

Soluzione

Ogni percorso è una sequenza di $8$ passi, di cui $5$ del tipo «Destra» (D) e $3$ del tipo «Basso» (B): una parola come $DDBDBDDB$. Il numero di percorsi è quindi il numero di anagrammi di questa parola, cioè il modo di scegliere quali $3$ degli $8$ passi sono «Basso»: $N = \binom{8}{3} = \frac{8\cdot 7\cdot 6}{6} = \boxed{56}.$

Collegamenti

Argomenti: Combinatoria
Concetti: Coefficiente binomiale · Combinazioni · Permutazioni
Metodi: Fattoriale permutazioni
Competenze: Calcolo combinatorio · Modellizzare
Tipo di esercizio: Problema combinatorio