Combinatoria ricorsiva

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Fast
Messaggi: 1
Iscritto il: 24 mar 2018, 18:12

Combinatoria ricorsiva

Messaggio da Fast » 24 mar 2018, 18:22

In quanti modi posso mettere in fila i numeri interi da 1 a 10 in modo da seguire le seguenti regole? :
-il primo numero della fila è sempre 1
-la differenza tra due posti che occupano posizioni consecutive non è mai superiore a 2
Riuscite a svolgerlo in modo ricorsivo? Se sì, potete scrivere il procedimento?

Ilgatto
Messaggi: 34
Iscritto il: 24 ott 2017, 16:36

Re: Combinatoria ricorsiva

Messaggio da Ilgatto » 10 nov 2018, 16:54

Visto che nessuno scrive da un po', comincia il necroposting.

Chiamo $P(n)$ il numero di modi di mettere in fila i primi $n$ numeri con quelle regole. I casi con $n$ piccolo si fanno a mano e li considero dopo. Se $n$ è maggiore di $3$ posso fare delle considerazioni di tipo ricorsivo. Il primo numero so che è $1$, poi posso avere un $2$ o un $3$.
Caso 1:
Se ho un $2$ ho poi $P(n-1)$ modi di completare con le altre cifre, in quanto è equivalente al caso $n-1$ ma devo mettere le cifre da $2$ a $n$ invece che da $1$ a $n-1$.
Caso 2.1:
Se invece ho un $3$ posso poi avere il $2$ e quindi il $4$ e completare dunque in $P(n-3)$ modi (stesso motivo di prima).
Caso 2.2:
Dopo il $3$ posso avere un $5$, ma così facendo devo proseguire fino a $n$ saltando un numero ogni volta (ad esempio passando da $5$ a $7$ poi $9$ eccetera) se $n$ è dispari; eventualmente se $n$ fosse pari posso mettere tutti i dispari fino a $n-1$ poi metto $n$ e torno indietro fino a $2$. Questo è evidentemente fattibile in un modo solo. Perchè mettendo il $5$ fisso tutte le mosse successive? Perchè se devo mettere il numero $2$ esso deve essere l'ultimo della sequenza in quanto può essere raggiunto solo dal $4$ e da esso posso raggiungere solo il $4$. Dunque l'ultimo numero della sequenza è $2$, il penultimo è $4$ e il terzultimo è $5$ (se $n=5$) o $6$ (se $n>5$). Proseguendo in questo modo ottengo che tutte le mosse sono obbligate da quando metto il $5$ come terzo numero.
Caso 2.3:
Se il terzo numero fosse $4$, o $n=4$ e concludo con un $2$ o $n>4$ e mettendo un $6$ o un $2$ ho che l'altro numero non può più essere messo nella sequenza in quanto dopo il $2$ non posso mettere altri numeri e nessun numero maggiore di $5$ dista meno di $2$ da $2$.

Concludo dunque che $P(n)=P(n-1)+P(n-3)+1+0$ per $n>3$ sommando semplicemente i risultati ottenuti nei vari casi analizzati sopra. Calcolo facilmente che:
$P(1)=1$
$P(2)=1$
$P(3)=2$
Dopo qualche passaggio ricavo anche che $P(10)=46$. Probabilmente esiste una formula chiusa per la successione, ma con quel $+1$ io non so come possa essere calcolata.

Rispondi