scacchiera 8x8

[tartaglia_2017]

ciao a tutti, vorrei che qualcuno mi da una mano con questo esercizio di calcolo combinatorio:
es. una pulce si trova sulla casella in basso a sinistra di una scacchiera standard 8x8 e deve andare alla casella diagonalmente opposta, effettuando 16 salti tra caselle contigue( cioè aventi un lato in comune). quanti sono i diversi percorsi che può fare?
grazie mille in anticipo.

[Luke99]

Le mosse possibili sono 2 : o va in su oppure a destra chiama S la mossa su e D quella destra i possibili modi sono tutte le permutazioni della stringa SSSSSSSSDDDDDDDD cioé[tex]\binom{16}{8}[/tex]

[tartaglia_2017]

ciao luke, scusa se ti ho risposto solo ora ma la risposta è 160160, quindi la tua è sbagliata......

[Luke99]

Hai ragione, é perché ho considerato una scacchiera 9x9, ci riprovo più tardi con quella giusta hahah

[Salvador]

Sei sicuro che sia 160160? A me esce 180180...

[Salvador]

Ho fatto questi ragionamento...

Testo nascosto:

Per poter arrivare alla casella finale la pulce deve compiere almeno 7 salti a destra e 7 in alto. Inoltre non può compiere un ulteriore salto a destra o in alto senza compiere un altro in direzione opposta: detto S un salto a sinistra, D uno a destra, A uno in alto e B uno in basso, si possono avere le due seguenti configurazioni: 8A+1B+7D oppure 8D+1S+7A.
Ovviamente né il primo né l'ultimo salto possono essere a sinistra o in basso. Consideriamo la prima configurazione: vi sono 4 possibilità:
- il primo e l'ultimo salto sono entrambi verso destra: ciò significa che dei restanti 14 salti 8 sono in alto, 1 in basso e 5 a destra, per i quali si hanno $\dfrac{14!}{8!5!1!}=18018$ percorsi possibili;
- il primo salto è a destra e il secondo in alto o viceversa oppure il primo e il secondo sono entrambi verso l'alto: in ogni caso vi sono $\dfrac{14!}{7!6!1!}=24024$ possibilità, e in totale 3*24024=72072 possibilità
Vi sono dunque in totale 18018+72072=90090 possibilità.
La seconda configurazione è "simmetrica" alla prima, per cui ripetendo lo stesso ragionamento si ottengono altri 90090 percorsi.
In totale vi sono dunque 180180 percorsi.

C'è qualche errore?

[teodella99]

Devi stare attento che non si esca mai dalla scacchiera

[Gizeta]

Confermo il risultato di Salvador.
Per hintare in maniera non eccessivamente rivelatoria posso dire che il risultato può essere scritto nella forma

[tex]\displaystyle \boxed{4 \sum_{i=0}^7{\left ( (14-i)\binom{13-i}{6} \right)}}[/tex]

dove il fattore [tex]4[/tex] salta fuori da un'osservazione sulle configurazioni.
Su richiesta posso dare indicazioni più precise.

---------------

Hint configurazione

Testo nascosto:

[Dudin]

Nope fa 160160

[mr96]

Testo nascosto:

[tex]2\left(\frac{16!}{7!\cdot 8!}-\frac{2\cdot 16!}{9!\cdot 7!}\right)[/tex] dove il primo termine sono i percorsi totali del tipo 8 passi a destra, uno a sinistra, e 7 in alto, mentre il secondo termine sono i due casi in cui esco dalla tabella (facendo uno step a sinistra prima del primo a destra o facendo tutti quelli a destra prima di quello a sinistra). Il 2 davanti è per simmetria con l'altro caso (8 alto, 1 basso, 7 destra)