Combinatoria ricorsiva

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Combinatoria ricorsiva

Messaggioda Filippo 01 » 24/03/2018, 14:21

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?
Filippo 01
 
Messaggi: 1
Iscritto il: 22/02/2018, 17:10

Re: Combinatoria ricorsiva

Messaggioda ronny » 30/07/2019, 9:54

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?
ronny
 
Messaggi: 24
Iscritto il: 20/04/2019, 23:28


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite