Question

چند کلمه با طول n وجود دارد که با حروف {a, b, c} ساخته شود به طوری که هیچ گاه بلافاصله بعد از حرف "b" حرف "c" نیامده باشد ؟ ( کلمه می تواند با معنی و یا بدون معنی باشد )

به عنوان مثال "bac" قابل پذیرش ولی "abc" قابل پذیرش نیست.

Answer 1

• با کمی تلاش می توانید دنباله باز گشتی $ x_{n} $ را بیابیم $ x_{n} $ تعداد کلمات بطول $n$ $$ x_{1} =3\;,\; x_{2} =8\; ,\;x_{n+2}= 3x_{n+1} - x_{n} $$ با حل معادله مشخصه $ x^2-3x+1=0 $ داریم $$ x_{n} =A( \frac{3+ \sqrt{5} }{2} )^{n+1} +B( \frac{3-\sqrt{5} }{2} )^{n+1} $$
• با استفاده از دو جمله اول دنباله خواهیم داشت $$A=-B= \frac{ \sqrt{5} }{5} $$
• بنابراین جواب سوال بصورت زیر است.

$$ x_{n} = \frac{ \sqrt{5} }{5} ( \frac{3+ \sqrt{5} }{2} )^{n+1} - \frac{ \sqrt{5} }{5} ( \frac{3-\sqrt{5} }{2} )^{n+1} $$