Prendiamo una tabella con $ x\ \ righe $ e $ x+y\ \ colonne $. (x,y nonnegativi).
Coloriamo di bianco le prime $ y+1\ $ caselle della prima riga,
le prime $ y+2 $ caselle della seconda...
...
fino a tutte quelle dell'ultima (x-esima).
Le restanti le coloriamo di nero.
Trovare una formula chiusa per contare il numero dei percorsi che partono nella casella in alta a sx e terminano in basso a dx passando solo per le caselle bianche, potendo passare di casella in casella con 2 sole mosse:
-giù di una; - a dx di una.
Percorsi, formula.
Percorsi, formula.
Ultima modifica di ghilu il 20 feb 2010, 21:10, modificato 1 volta in totale.
Non si smette mai di imparare.
posso chiederti una delucidazione sul testo?
se le colonne sono $ x + y $ ; e le caselle che coloriamo di bianco per ogni riga sono $ y + 2 $ ; a meno che $ x $ non sia uguale a $ 2 $, il numero di colonne è magigore al numero di caselle colorate; e perciò le caselle $ y+2<n<x+y $ saranno obbligatoriamente nere, allora come faccio ad arrivare ad una casella nera se posso passare solo dalle bianche?
se le colonne sono $ x + y $ ; e le caselle che coloriamo di bianco per ogni riga sono $ y + 2 $ ; a meno che $ x $ non sia uguale a $ 2 $, il numero di colonne è magigore al numero di caselle colorate; e perciò le caselle $ y+2<n<x+y $ saranno obbligatoriamente nere, allora come faccio ad arrivare ad una casella nera se posso passare solo dalle bianche?
(x+y su x) - (x+y+1 su x-1)
ora sono molto stanco quindi scrivo veloce:
tutti i percorsi possibili su un normale rettangolo (x+y) per (x) sono (x+y su x) a cui devo togliere le mosse "illecite" ossia ke passano sul nero.
allora faccio ke da quando arrivo sulla prima casella illecita del mio persorso faccio la mossa opposta a quella ke dovrei fare ossia se devo andare giù vado a destra e se devo andare a destra vado giù, in questo modo creo un percorso alternativo ke esce dal percorso normale circa in questo modo
quindi tutti i percorsi illeciti sono tutti i percorsi di lunghezza x+y+1 e larghezza x-1 da cui la formula (x+y su x) - (x+y+1 su x-1)
ora sono molto stanco quindi scrivo veloce:
tutti i percorsi possibili su un normale rettangolo (x+y) per (x) sono (x+y su x) a cui devo togliere le mosse "illecite" ossia ke passano sul nero.
allora faccio ke da quando arrivo sulla prima casella illecita del mio persorso faccio la mossa opposta a quella ke dovrei fare ossia se devo andare giù vado a destra e se devo andare a destra vado giù, in questo modo creo un percorso alternativo ke esce dal percorso normale circa in questo modo
quindi tutti i percorsi illeciti sono tutti i percorsi di lunghezza x+y+1 e larghezza x-1 da cui la formula (x+y su x) - (x+y+1 su x-1)
a me sinceramente venivano numeri diversi e una soluzione solo abbozzata...(x+y su x) - (x+y+1 su x-1)
ora sono molto stanco quindi scrivo veloce:
tutti i percorsi possibili su un normale rettangolo (x+y) per (x) sono (x+y su x) a cui devo togliere le mosse "illecite" ossia ke passano sul nero.
allora faccio ke da quando arrivo sulla prima casella illecita del mio persorso faccio la mossa opposta a quella ke dovrei fare ossia se devo andare giù vado a destra e se devo andare a destra vado giù, in questo modo creo un percorso alternativo ke esce dal percorso normale circa in questo modo
quindi tutti i percorsi illeciti sono tutti i percorsi di lunghezza x+y+1 e larghezza x-1 da cui la formula (x+y su x) - (x+y+1 su x-1)
anche io avevo cominciato vedendo tutti i possibili percorsi in un rettangolo (X; X+Y) e mi venivano (2X+Y-2) su (X-1) il latex scarseggia.. per poi sottrarre quelle che passavano per il nero
ma a testimoniare l'inutilità dle mio primo passaggio
poi avevo pensato che i percorsi accettabili sono quelli che se soddisfano la seguente condizione:posso fare l'N-esimo passo verso destra (->) solo se ho già fatto almeno [N(->) - Y ] passi verso il basso... poi ora bisognerebbe calcolare quanti sono
