5
$\begingroup$

How many $N$ digits binary numbers can be formed where $0$ is not repeated. Note - first digit can be $0$.

I am more interested on the thought process to solve such problems, and not just the answer.
If anyone can cite some resources for learning how to solve such problems would be great.

  • 0
    An interesting sidenote : for n = 2,3,4,5 this relation holds : n + 2^(n-2). I was asked this question in an interview and made the mistake of starting with above relation and trying to prove it by induction :-).2016-03-04

2 Answers 2

6

First consider $B_{a}(n)$ as the number of "binary number" without 0 repeated of length $n$, which starts with $a$, with $a \in \left\{0, 1\right\}$. Then: $B(n) = B_{0}(n) + B_{1}(n)$ is the number of "binary number" without 0 repeated of length $n$.

We can know work on the $B_{a}(n+1)$. These number can build by adding $0$s or $1$s in front of a number of length $n$. In particular we have that: $B_{0}(n+1) = B_{1}(n) \\ B_{1}(n+1) = B_{0}(n) + B_{1}(n) = B(n)$

Summing up, we have that: $B(n+1) = B(n) + B_{1}(n)$

But it also clear from the previous relation that $B_1(n) = B(n-1)$ (since $B_{1}(n+1) = B(n)$ is true for $n$, then it is true even for $n-1$), so we finally have the recurrence relation: $B(n+1) = B(n) + B(n-1)$

At this point you have to determinate the number $B(1)$ and $B(2)$ and then apply the recurrence relation we have derived before.

We have $B(1) = 2$, since we have the sequences $[0]$ and $[1]$. Also, $B(2) = 3$, since we have the sequences $[0,1]$, $[1,0]$ and $[1,1]$.

So we can evaluate $B(3) = B(2) + B(1) = 5$ and so on.

Note: the recurrence relation is the same of the Fibonacci sequence.

  • 0
    well, actually I followed a lecture about those kind of problem and I don't know where to send you for further reading. However, the general trick is to think "how to build an object with parameter $\theta+1$ knowing that I already built the object with parameter $\theta$"... The wrong way (but not always wrong!) is to pretend to build the object by exploiting its internal structure for a fixed parameter $\theta$. By the way, in our case, the parameter $\theta$ is simply $n$.2012-12-18
3

One way to solve problems like this is with recurrence relations. If we let $a_n$ denote the number of binary words of length $n$ without adjacent $0$s, then we can derive a relationship between $a_n$ and the values $a_{n-1}$ and $a_{n-2}$.

In fact, we see that either the first digit is a $1$ or the first two digits are $01$, without any further constraints on the sequence. Thus $ a_n = a_{n-1} + a_{n-2} $ because these two cases are the only possibilities. Then, if you supply the "initial conditions" for $a_1$ and $a_2$, this gives a formula for $a_n$ by techniques given in the link above.

To learn more about this kind of technique, I would recommend the book by Graham, Knuth, and Patashnik "Concrete Mathematics: A Foundation for Computer Science". Many books and courses on discrete mathematics or enumerative combinatorics can also help.

  • 0
    @BrianM.Scott ya thanks but i am really weak at such problems.2012-12-18