Scacchiera

Complessivamente la pulce dovrà percorrere 8 tratti: 3 spostandosi nelle caselle in basso a sinistra e 5 spostandosi nelle caselle in basso a destra volta per volta. Quindi il calcolo è quello delle Combinazioni semplici:

COMB(8, 3) = COMB(8, 5) = 56 modi

In generale per scacchiera infinita, possiamo dire che:

COMB(h+k, h) = COMB(h+k, k)=(h+k)!/(h!k!)

(legge dei tre fattoriali)

Un altro modo risolutivo è quello di considerare le permutazioni con ripetizione (gli anagrammi)

La pulce ad esempio per andare da (0,0) a (3,5) senza risalire, può percorrere ad esempio la strada:

SSSDDDDD ( la pulce può andare a destra oppure a sinistra: a sinistra S per 4 volte, cioè si ripete 4 volte, oppure a destra per 6 volte, cioè si ripete 6 volte). Quindi permutazioni con ripetizione di 8 elementi di cui S si ripete 3 volte e D si ripete 5 volte:

Quini il numero di possibili camminamenti è pari a:

8!/(3!·5!) = 56