AnswerBun.com

There are $6$ digits containing $1$ and $0$, only problem is that $0$'s can't be next to each other

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?

One Answer

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

Add your own answers!

Related Questions

Fundamental group of Klein Bottle

2  Asked on December 15, 2021 by jos-luis-camarillo-nava

         

Lottery – Probability Discrepancy

2  Asked on December 15, 2021 by cannon444

         

Find locus of point

0  Asked on December 15, 2021

     

about the Laguerre square expansion Sin(x)

0  Asked on December 13, 2021 by charlessilva

   

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir