Probabilità numeri binari

[maschinna]

Salve,
è da un po' di giorni che ragiono su un quesito di calcolo delle probabilità, preso da un concorso per la triennale in matematica tenutosi l'anno scorso. Il testo è semplice:
Stabilire quanti sono i numeri interi n, con $ 0<=n <= 1023 $ , nella cui rappresentazione binaria non
compaiono sequenze di 3 cifre consecutive uguali a 1.

Allora. Io ho pensato che i 1024 numeri potessero essere scritti combinando lo 0 e l'1 per 10 volte ($2^10$). Ma come considerare nelle combinazioni le sequenze di tre 1?
Grazie

Le opzioni sono: 484, 504, 511, 512, 576.

[nino_12]

Il risultato è $504$

Mentre i casi totali (in binario) sono $2^n$ con $n=1,2,...$

quelli favorevoli, cioè con $0,1,2$ consecutività del segno $1$ senza limiti per gli $0$ sono i numeri di Tribonacci:
$2, 4, 7, 13, 24, 44, 81, 149, 274,$ $504$$, 927, ...$

http://oeis.org/A000073

[maschinna]

Grazie!
Ma come fa uno studente liceale a sapere che in questo caso si devono usare i numeri di Tribonacci? Non c'è un altro metodo, anche se più laborioso?

[nino_12]

"Maschinna":
Ma come fa uno studente liceale a sapere che in questo caso si devono usare i numeri di Tribonacci? Non c'è un altro metodo, anche se più laborioso?

Si possono togliere da tutti i casi possibili ($2^10$), quelli che contengono sequenze di almeno 3 segni 1 consecutivi.

(X = 0 oppure 1)

$111XXXXXXX = 2^7$

$0111XXXXXX = 2^6$

$X0111XXXXX = 2^6$

$XX0111XXXX = 2^6$

$aaa0111XXX = 7*2^3$ (aaa esclude 111)

$aaaa0111XX = 13*2^2$ (aaaa esclude 1111; 1110; 0111)

$aaaaa0111X = 24*2$ (aaaaa esclude 8 casi: 111XX; 0111X; X0111)

$aaaaaa0111 = 44 * 1$ (aaaaaa esclude 20 casi: 111XXX; 0111XX; X0111X; XX0111)

Quindi: $1024-128-3*64-7*8-13*4-24*2-44 = 504$

In realtà, basterebbe esaminare i primi casi (n = 1...2...3...4...5) per rendersi conto che i valori accettabili (quelli con 0-1-2 segni 1 consecutivi) sono:

$n=1 ----> 2$

$n=2 ----> 4$

$n=3 ----> 7$

$n=4 ---->13$

$n=5 ---->24$

....

e la sequenza prosegue facendo la somma dei tre termini precedenti:

$a(n+1) = a(n) + a(n-1) + a(n-2)$

Quindi:
$a(6) = 24+13+7 = 44$
$a(7) = 81$
$a(8) = 149$
$a(9) = 274$

$a(10) = 504$