2
$\begingroup$

Restrictions:

  1. First and the last digit has to be 1.
  2. Contain no two consecutive 1's and
  3. Contain no three consecutive 0's

From my observation first two and last two digits will be fixed as 10 and 01, because it can't be 11... or ...11. So we got n-4 places left to fill. Apart from the first 2 and last 2 places if we add one more space then that space can only have 1, not 0. If we add one more place then there are two possible way (100101, 101001). So that's what I got For

n=6 2 ways
n=7 2 ways
n=8 3 ways
n=9 4 ways

I don't know if I am doing it right or not and what's the easy way to find the number of ways for this scenario rather than counting. I would appreciate some guidance for a general rule of a binary string of length n that do not contain 3 consecutive 0's and 2 consecutive 1's while starting and ending with 1

$\endgroup$
  • $\begingroup$ The question is not clear. I do not know why the first and last digit must be 1. Even assuming this, I do not know why the first two digits must be 10. It seems to me that 111111 satisfies the title requirements since it does not "contain 3 consecutive 0s and 2 consecutive 1s." So the use of the word and needs clarification (should it really be or?), and all assumptions need to be in the body of the question. $\endgroup$ – Michael Jan 31 at 17:35
  • $\begingroup$ @Michael will add more detail. Thanks $\endgroup$ – Khan Jan 31 at 17:45
2
$\begingroup$

I can find a recursive formula, but a general formula is tricky.

$f(x) = f(x-2) + f(x-3)$

That is because the pattern must start with 1, then you must have either one or two 0's before the next 1. In other words, 01 or 001.

Thus any sequence of length X is either (a valid sequence of length x-2 + 01) or (a valid sequence of length x-3 + 001)

For a general formula as a function of N, we can assume

$f(x)=\sum{n^x}$ for some values of a and then

$n^x=n^{x-2}+n^{x-3}$

Leaves $n$ as a root of the cubic equation $y^3-y-1=0$.

Thus $f(x) = a_1n_1^x + a_2n_2^x + a_3n_3^x$, where $n_1, n_2, n_3$ are the roots of the equation $x^3-x-1=0$. But since two of these roots are imaginary, it is a problem to find a specific formula that is non-messy.

In your case, we have

  • f(0) = 0 (trivial case)
  • f(1) = 1 (1)
  • f(2) = 0 (again trivial to check none work)
  • f(3) = 1 (1-01)
  • f(4) = 1 (1-001)
  • f(5) = 1 (101-01)
  • f(6) = 2 (101-001, 1001-01)
  • f(7) = 2 (1001-001, 10101-01)
  • f(8) = 2+1=3
  • f(9) = 2+2=4

So your calculations are right.

Your problem reminds me of an American Invitational Math Exam problem where you had to find the number of sequences of N coin flips with no 2 tails in a row. You could thus have either H or HT to create a list of length N+1, chopping off the starting H.

Then $g(x)=g(x-1)+g(x-2)$ and if we assume $g(x)=\sum{a^x}$ for some values of $a$, we get $a^n=a^n-1+a^n-2$, or $a^2=a+1$, making $a$ the golden ratio.

$\endgroup$
  • $\begingroup$ Thanks for a simple solution. I have seen some of the questions where the solution was based on the recursive formula. I still haven't understood this method completely. Can you please suggest some resources to learn this method? $\endgroup$ – Khan Feb 1 at 15:54
  • $\begingroup$ So suppose if the question was can start with 1 or 0 but no 3 0's and no 3 1's can be placed consecutively. Then any sequence which starts with 1 of length X is either a valid sequence of length x-1+0, x-1+1, x-2+01,x-2+10,x-2+11,x-3+001 or x-3+100. So f(x) = 2f(x-1)+3f(x-2)+2f(x-3)? Did I get it right? $\endgroup$ – Khan Feb 1 at 15:59
3
$\begingroup$

Ignoring the $1$ at the front, any such sequence can be broken into blocks of $01$ and $001$. Let $k$ be the number of blocks of $01$. Then the number of blocks of $001$ will be $(n-1-2k)/3$, which is only possible when this number is an integer. This means there are $(n-1-2k)/3+k=(n+k-1)/3$ blocks total. We must choose $k$ of these blocks to be $01$, which can be done in $\binom{(n+k-1)/3}k$ ways. Therefore, the number of sequences is $$ \sum_{\substack{k=0}}^{\lfloor (n-1)/2\rfloor}\binom{\frac{n+k-1}3}{k} $$ where the summation only ranges over $k$ for which $n+k-1$ is an integer multiple of $3$.

It is also possible to get a "closed form" by solving the linear recurrence $$ a_n=a_{n-2}+a_{n-3},\\ a_2=0,\\ a_1=1,\\ a_0=0. $$ To solve this, see for example:

https://en.wikipedia.org/wiki/Recurrence_relation#Roots_of_the_characteristic_polynomial.

$\endgroup$
  • $\begingroup$ But the roots of the characteristic equation are ugly. $\endgroup$ – saulspatz Jan 31 at 18:13
  • $\begingroup$ @saulspatz True. One of the roots $r\approx 1.3247$ is real, and the others are complex with magnitude less than $1$. For large enough $n$, you can therefore find $a_n$ by rounding $r^n$ to the nearest integer, which is a little nicer. $\endgroup$ – Mike Earnest Jan 31 at 18:16
  • $\begingroup$ Good point. I hadn't considered that. $\endgroup$ – saulspatz Jan 31 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.