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}$$