Combinatoria ricorsiva

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.
Rispondi
Filippo 01
Messaggi: 1
Iscritto il: 22/02/2018, 17:10

Combinatoria ricorsiva

Messaggio da Filippo 01 »

In quanti modi posso mettere in fila i numeri interi da 1 a 10 in modo da seguire le seguenti regole? :
- Il primo numero è sempre 1
- La differenza tra due posti che occupano posizioni consecutive non è mai superiore a 2
Riuscite a risolverlo in maniera ricorsiva? Se sì potete scrivere il procedimento?
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Combinatoria ricorsiva

Messaggio da ronny »

Ci provo:

Primo numero 1 e poi devo mettere in fila 9 numeri usando solo la regola 2:
- scelgo il numero 2 e poi devo mettere in fila i rimanenti 8 numeri da 3 a 10. Chiamo questo valore [tex]A_8[/tex]
- scelgo il numero 3, quindi il successivo deve per forza essere il 2 (altrimenti poi il 2 diventa troppo lontano per tutti i numeri rimantenti) e quindi rimangono 7 numeri consecutivi da
scegliere con l'algoritmo ricorsivo, cioè [tex]A_7[/tex]

Quindi [tex]A_{9} = A_8 + A_7[/tex], in generale [tex]A_{n} = A_{n-1} + A_{n-2}[/tex] con [tex]A_2 = 2[/tex] e [tex]A_1 = 1[/tex]
In pratica una successione di Fibonacci che inizia da 1 e 2 invece che da 0 e 1

Si calcola anche a mano [tex]A_{9} = 55[/tex]

Sai se il risultato è giusto?
Rispondi