Question

Có bao nhiêu xâu nhị phân có độ dài n trong đó không có hai bit 1 đứng cạnh nhau?

Answer 1

 Gọi \(c_n\) là số xâu nhị phân có độ dài \(n\) thỏa mãn điều kiện đề bài.

Ta có: \(c_1=2; \ c_2=3.\)

Xét xâu nhị phân có độ dài \(n\) thỏa mãn điều kiện đề bài có dạng \(a_{n}a_{n-1}a_{n-2}...a_{2}a_{1}.\)

Có hai trường hợp:

TH1: \(a_n=1. \) Khi đó \(a_{n-1}=0\) và \(a_{n-2}...a_2a_1\) có thể chọn là một xâu bất kỳ độ dài \(n-2\) thỏa điều kiện. Có \(c_{n-2}\) xâu như vậy, suy ra trường hợp này có \(c_{n-2}\) xâu.

TH2: \(a_n=0\). Khi đó \(a_{n-1}...a_2a_1\) có thể chọn là một xâu bất kỳ độ dài \(n-1\) thỏa điều kiện. Có \(c_{n-1}\) xâu như vậy, suy ra trường hợp này có \(c_{n-1}\) xâu.

Vậy tổng cộng xây dựng được \(c_{n-1}+c_{n-2}\) xâu hay \(c_n=c_{n-1}+c_{n-2}.\)

\(\Rightarrow c_n=\dfrac{\sqrt5-2}{\sqrt5} \begin{pmatrix} \dfrac{1-\sqrt5}{2} \end{pmatrix}^{n-1}+\dfrac{2-\sqrt5}{\sqrt5} \begin{pmatrix} \dfrac{1+\sqrt5}{2}\end{pmatrix}^{n-1}\)