Una successione strettamente crescente di numeri interi si dice a parità alterna se comincia con un numero dispari, ha come secondo termine un numero pari, poi un dispari, e così via. La lista vuota è considerata a parità alterna. Indichiamo con $ A(n) $ l'insieme delle liste a parità alterna contenute in $ {1,...,n} $, con $ P(n)=Card A(n) $ il loro numero.
Esprimere $ P(n) $ mediante una formula ricorrente.
Problema di combinatoria
Problema di combinatoria
Aboliamo il latino nei licei scientifici!
io lo stavo provando a fare e in realtà mi fermo abbastanza presto:
$ P(n)=P(n-1)+Q(n-1) $ dove $ Q(n-1) $ è la cardinalità dell'insieme delle liste a parità alterna che finiscono con un pari se n è dispari e con un dispari se n è pari...
ora però il problema si sposta su $ Q(n) $...
la lista vuota la considero come se finisse con un pari...
$ P(n)=P(n-1)+Q(n-1) $ dove $ Q(n-1) $ è la cardinalità dell'insieme delle liste a parità alterna che finiscono con un pari se n è dispari e con un dispari se n è pari...
ora però il problema si sposta su $ Q(n) $...
la lista vuota la considero come se finisse con un pari...
Beh, in realtà la fine è vicina:
$ Q(n) = P(n-1) $
infatti si può fare una corrispondenza biunivoca fra le liste a parità alterna in
$ M=\{1,...,n-1\} $
e le liste a parità alterna in
$ N=\{1,...,n\} $
che finiscono con un numero con la stessa parità di n.
Possiamo farlo vedere velocemente chiamando $ A $ un numero minore di $ n $ che ha la sua stessa parità
e chiamando $ B $ uno con diversa parità:
$ M: $ lista che finisce con $ A $ <---> $ N: $ stessa lista, che finisce con $ A $.
$ M: $ lista che finisce con $ B $ <---> $ N: $ stessa lista, che finisce con $ B $ , ma con alla fine il numero $ n $.
$ Q(n) = P(n-1) $
infatti si può fare una corrispondenza biunivoca fra le liste a parità alterna in
$ M=\{1,...,n-1\} $
e le liste a parità alterna in
$ N=\{1,...,n\} $
che finiscono con un numero con la stessa parità di n.
Possiamo farlo vedere velocemente chiamando $ A $ un numero minore di $ n $ che ha la sua stessa parità
e chiamando $ B $ uno con diversa parità:
$ M: $ lista che finisce con $ A $ <---> $ N: $ stessa lista, che finisce con $ A $.
$ M: $ lista che finisce con $ B $ <---> $ N: $ stessa lista, che finisce con $ B $ , ma con alla fine il numero $ n $.
Altrimenti, se non viene subito questa idea (è lecito che non venga: non è astrusa, ma bisogna pensarci un attimino per averla; magari può venire affrontando il problema da un altro punto di vista, più ordinato), si può ragionare come segue:
dal messaggio di gian92 si capisce che, a complicare il problema, intervengono 2 cose:
-distinzione n pari e n dispari.
-liste che finiscono con pari e liste che terminano con dispari.
Il consiglio è: "divide et impera".
Sia $ A(n) $ il numero delle liste a parità alterna che terminano con un pari.
Sia $ B(n) $ il numero delle liste a parità alterna che terminano con un dispari.
Scopriamo come sono collegati e poi ricaviamo:
$ P(n)= A(n)+B(n) $
$ A(2n+1) = A(2n) $ perchè le liste contate da $ A(2n+1) $ non possono finire con $ 2n+1 $.
Analogamente: $ B(2n)=B(2n-1) $.
D'altra parte:
$ A(2n) = $ n° liste che terminano con un pari minore o uguale a (2n-1) +
+ n°liste che terminano con 2n.
$ = A(2n-1) $ più le liste che terminano con un dispari minore od uguale a (2n-1) seguito da 2n.
Quindi: $ A(2n) = A(2n-1)+ B(2n-1) = P(2n-1) $.
Analogamente: $ B(2n+1) = B(2n) + A(2n) = P(2n) $.
Decoupage:
$ P(2n) = A(2n)+ B(2n) = P(2n-1) + B(2n-1) = P(2n-1) + P(2n-2) $
$ P(2n+1) = A(2n+1)+ B(2n+1) = A(2n) + P(2n) = P(2n-1) + P(2n) $
La risposta, dunque, dovrebbe essere:
$ P(x) = P(x-1) + P(x-2) $
e qualche passo base.
Circa o forse esattamente Fibonacci.
dal messaggio di gian92 si capisce che, a complicare il problema, intervengono 2 cose:
-distinzione n pari e n dispari.
-liste che finiscono con pari e liste che terminano con dispari.
Il consiglio è: "divide et impera".
Sia $ A(n) $ il numero delle liste a parità alterna che terminano con un pari.
Sia $ B(n) $ il numero delle liste a parità alterna che terminano con un dispari.
Scopriamo come sono collegati e poi ricaviamo:
$ P(n)= A(n)+B(n) $
$ A(2n+1) = A(2n) $ perchè le liste contate da $ A(2n+1) $ non possono finire con $ 2n+1 $.
Analogamente: $ B(2n)=B(2n-1) $.
D'altra parte:
$ A(2n) = $ n° liste che terminano con un pari minore o uguale a (2n-1) +
+ n°liste che terminano con 2n.
$ = A(2n-1) $ più le liste che terminano con un dispari minore od uguale a (2n-1) seguito da 2n.
Quindi: $ A(2n) = A(2n-1)+ B(2n-1) = P(2n-1) $.
Analogamente: $ B(2n+1) = B(2n) + A(2n) = P(2n) $.
Decoupage:
$ P(2n) = A(2n)+ B(2n) = P(2n-1) + B(2n-1) = P(2n-1) + P(2n-2) $
$ P(2n+1) = A(2n+1)+ B(2n+1) = A(2n) + P(2n) = P(2n-1) + P(2n) $
La risposta, dunque, dovrebbe essere:
$ P(x) = P(x-1) + P(x-2) $
e qualche passo base.
Circa o forse esattamente Fibonacci.