Gli Indam 2009 più carucci 2
Gli Indam 2009 più carucci 2
Trovare il numero di stringhe lunghe n di T e C in cui non compaiono mai due T adiacenti.
Avete presente la serie di Fibonacci?
$ A_0=0 $
$ A_1=1 $
$ A_n=A_{n-1}+A_{n-2} $
Ecco, ho notato che la soluzione di questo problema é $ A_{n+2} $.
Infatti con $ n=1 $ abbiamo $ k=2 $(dove n indica la lunghezza della stringa, e k il risultato)
n=1 --> k=2 (1+1)
n=2 --> k=3 (1+2)
n=3 --> k=5 (1+3+1)
n=4 --> k=8 (1+4+3)
n=5 --> k=13(1+5+6+1)
n=n --> $ k=\binom{n}{n} + \binom{n}{n-1} + [\binom{n}{n-2} - \binom{n-1}{n-2}] + [\binom{n}{n-3} - \binom{n-2}{n-3}] $...
Il principio per ricavare questa formula è questo: aggiungere tutte le combinazioni di lunghezza n con esattamente $ (n-x) $ C; e sottrarre tutte le combinazioni di lunghezza n con $ x $ T consecutive, trattando queste T come dei blocchi indivisibili.
Forse la mia soluzione risulta difficile da capire, ma non so spiegarmi bene e adesso non ho tempo, mi dispiace.
$ A_0=0 $
$ A_1=1 $
$ A_n=A_{n-1}+A_{n-2} $
Ecco, ho notato che la soluzione di questo problema é $ A_{n+2} $.
Infatti con $ n=1 $ abbiamo $ k=2 $(dove n indica la lunghezza della stringa, e k il risultato)
n=1 --> k=2 (1+1)
n=2 --> k=3 (1+2)
n=3 --> k=5 (1+3+1)
n=4 --> k=8 (1+4+3)
n=5 --> k=13(1+5+6+1)
n=n --> $ k=\binom{n}{n} + \binom{n}{n-1} + [\binom{n}{n-2} - \binom{n-1}{n-2}] + [\binom{n}{n-3} - \binom{n-2}{n-3}] $...
Il principio per ricavare questa formula è questo: aggiungere tutte le combinazioni di lunghezza n con esattamente $ (n-x) $ C; e sottrarre tutte le combinazioni di lunghezza n con $ x $ T consecutive, trattando queste T come dei blocchi indivisibili.
Forse la mia soluzione risulta difficile da capire, ma non so spiegarmi bene e adesso non ho tempo, mi dispiace.