Problema di combinatoria
Ho un poccolo problema di programmazione dinamica e alla base serve applicare il calcolo combinatorio. Quante sono le stringhe di lunghezza n in cui non compaiono mai tre uni consecutivi? Ho testato che:
T[1]=2
T[2]=4
T[3]=7
T[n]=T[n-3]+T[n-2]+T[n-1] con n>3.
Potreste spiegarmi come si risolve con le disposizioni o qualche altro metodo?
Grazie in anticipo
T[1]=2
T[2]=4
T[3]=7
T[n]=T[n-3]+T[n-2]+T[n-1] con n>3.
Potreste spiegarmi come si risolve con le disposizioni o qualche altro metodo?
Grazie in anticipo
Risposte
Un dimostrazione 'ruspante' potrebbe essere questa.
Raggruppando le stringhe secondo le due cifre finali, consideriamo i vettori v(n) che riportano il numero di stringhe di lunghezza n soddisfacenti la condizione e terminanti, rispettivamente, per 00, 01,10 e 11.
Deve essere, con $ i>1 $: $ v(i+1,1)=v(i+1,2)=v(i,1)+v(i,3); v(i+1,3)=v(i,2)+v(i,4); $ $ v(i+1,4))=v(i,2). $ (se una stringa termina per 11 non è possibile continuare con un ulteriore 1).
Allora posto $ v(j)=[a,b,c,d] $ sarà:
$ v(j+1)=[a+c,a+c,b+d, b] $
$ v(j+2)=[a+b+c+d, a+b+c+d, a+b+c, a+c] $
$ v(j+3)=[2a+2b+2c+d, 2a+2b+2c+d, 2a+b+2c+d, a+b+c+d] $.
Da cui, sommando le componenti si ottiene $ T(j)=a+b+c+d; T(j+1)=2a+2b+2c+d; T(j+2)=4a+3b+4c+2d;$
$ T(j+3)=7a+6b+7c+4d=T(j)+T(j+1)+T(j+2); $
che equivale alla legge ricorsiva proposta con $ n>5 $. Per completare la dimostrazione basterà verificarla nei casi iniziali mancanti.
Ciao
Raggruppando le stringhe secondo le due cifre finali, consideriamo i vettori v(n) che riportano il numero di stringhe di lunghezza n soddisfacenti la condizione e terminanti, rispettivamente, per 00, 01,10 e 11.
Deve essere, con $ i>1 $: $ v(i+1,1)=v(i+1,2)=v(i,1)+v(i,3); v(i+1,3)=v(i,2)+v(i,4); $ $ v(i+1,4))=v(i,2). $ (se una stringa termina per 11 non è possibile continuare con un ulteriore 1).
Allora posto $ v(j)=[a,b,c,d] $ sarà:
$ v(j+1)=[a+c,a+c,b+d, b] $
$ v(j+2)=[a+b+c+d, a+b+c+d, a+b+c, a+c] $
$ v(j+3)=[2a+2b+2c+d, 2a+2b+2c+d, 2a+b+2c+d, a+b+c+d] $.
Da cui, sommando le componenti si ottiene $ T(j)=a+b+c+d; T(j+1)=2a+2b+2c+d; T(j+2)=4a+3b+4c+2d;$
$ T(j+3)=7a+6b+7c+4d=T(j)+T(j+1)+T(j+2); $
che equivale alla legge ricorsiva proposta con $ n>5 $. Per completare la dimostrazione basterà verificarla nei casi iniziali mancanti.
Ciao
Non c'é un modo piú intuitivo? Io non sono un matematico -.-
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo