Percorsi su una griglia quadrata

Immaginiamo un quadrato di lato unitario. Per semplicità sovrapponiamolo a un sistema di assi cartesiani in modo che il vertice in basso a sinistra coincida con l’origine, cioè abbia coordinate (0, 0), e il vertice in alto a destra sia situato nel primo quadrante, dunque con coordinate (1, 1). Quanti sono i possibili percorsi di lunghezza totale 2 per andare da (0, 0) a (1, 1)? I percorsi sono due: si può procedere prima verso est e poi verso nord, oppure prima verso nord e poi verso est. Schematizzando possiamo scrivere:

EN
NE

Cosa succede se il quadrato ha lato 2 e vogliamo andare dal punto (0, 0) al punto (2, 2) con percorsi di lunghezza totale 4 e tratte unitarie? In questo caso i percorsi possibili sono 6:

NNEE
NENE
NEEN
ENNE
ENEN
EENN

Bene, a questo punto è il caso di chiedersi se esiste una formula di validità generale. Fortunatamente la risposta è affermativa.
Se su una griglia quadrata di lato a si parte dall’origine il punto di coordinate (a, a) può essere raggiunto con P(a, a) = (a + a)!/(a!a!) percorsi diversi di lunghezza a + a e tratte unitarie.

Ecco il valori di P(1, 1), P(2, 2), …, P(8, 8):

P(1, 1) = 2
P(2, 2) = 6
P(3, 3) = 20
P(4, 4) = 70
P(5, 5) = 252
P(6, 6) = 924
P(7, 7) = 3.432
P(8, 8) = 12.870

L’ultimo esempio si può interpretare come segue: una formica che parte dal vertice in basso a sinistra di una scacchiera potrebbe raggiungere il vertice opposto in alto a destra in 12.870 modi diversi. Se poi rimuovessimo la condizione di avere percorsi di lunghezza 16 i modi sarebbero ancor più numerosi.

Se a qualcuno questi numeri dovessero risultare familiari è perché lo sono: si tratta, infatti, dei coefficienti binomiali centrali, ovvero i numeri allineati sulla verticale del triangolo di Pascal/Tartaglia.

Advertisements

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...