Mathematics Asked by Yağız Alp Ersoy on November 29, 2020

Imagine this: There are $6$ digits which can contain either $1$ or $0$. For example: $100110$

Only problem is that $0$‘s can’t be next to each other. For example, $101101$ is fine.

How many combinations are there that is a no-no and how many combinations that are fine?

Let's follow tkf's answer.

Let $a_n$ be the number of sequences of length $n$ ending in $1$ and $b_n$ be the number of sequences of length $n$ ending in $0$. Suppose my sequence ends in $1$. Then I could add either a $0$ or a $1$. However, if my sequence ends in $0$, I can only add a $1$. So

$$a_{n+1} = a_n + b_n,$$ $$b_{n+1} = a_n.$$ Now if we know $a_1 = 1$, $b_1 = 1$, let's determine $a_6$. We have

$$a_2 = 2, b_2 = 1, a_3 = 3, b_3 = 2, a_4 = 5, b_4 = 3, a_5 = 8, b_5=5, a_6 = 13, b_6=8.$$

Here's a question: Can you tell me what $a_n$ and $b_n$ are for any $n$?

Regardless, the total number of admissable sequences will be $a_6 + b_6 = 21$. The total number of sequences will be $2^6$ (why?) so the total number of nonadmissable sequences will be $2^6 - 21 = 43$.

Here's another way to think about it: Let $$ A = begin{pmatrix} 1 & 1 \ 1 & 0 end{pmatrix} = begin{pmatrix} a(1) & b(1) \ a(1) & 0 end{pmatrix}.$$ Then $$ A begin{pmatrix} 1 \ 1 end{pmatrix} =begin{pmatrix} a(1) + b(1) \ a(1) end{pmatrix} = begin{pmatrix} a(2) \ b(2) end{pmatrix}. $$

By inducting, we see

$$A^{n-1} begin{pmatrix} 1 \ 1 end{pmatrix} = begin{pmatrix} a(n) \ b(n) end{pmatrix}.$$ Let $|(a,b)^T| = a + b.$ Then

$$|A^{n-1} cdot (1,1)^T| = text{ total number of admissable sequences}.$$

Correct answer by User203940 on November 29, 2020

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP