2
$\begingroup$

I need to calculate the total number of possible binary strings of length $n$ with no two adjacent 1's.

Eg.
for n = 3
f(n) = 5
000,001,010,100,101

How do I solve it?

$\endgroup$
  • 2
    $\begingroup$ $f(n)=F_{n+2}$ where $F_n$ is the $n$-th Fibonacci number. Have also a look at en.wikipedia.org/wiki/Fibonacci_coding $\endgroup$ – Jack D'Aurizio May 13 '15 at 16:39
  • $\begingroup$ Permutation is probably not the best word to use here. It appears you are counting binary strings (or finite sequences of 0's and 1's) "with no two adjacent 1's". Permutation is often used by mathematicians to describe arrangements (or rearrangements) of distinct values. $\endgroup$ – hardmath May 13 '15 at 22:11
7
$\begingroup$

Hint: Use a recurrence relation. What if the string with $k$ bits starts with a 1, how many possibilities gives this for strings with $k+1$ bits? If the string with $k$ bits starts with a 0, how many possibilities gives this for strings with $k+1$ bits?

$\endgroup$
  • $\begingroup$ Thanks a lot, it makes sense and I could prove it to be Fibonacci series. I didn't know about Fibonacci coding earlier, otherwise it would have been obvious to me. $\endgroup$ – Naman May 13 '15 at 16:41
3
$\begingroup$

Mathematical Proof:

Let B(n) give the count of binary sequences of length n without adjacent 1's.

B(0) = 1 //There is exactly one way to list 0 items.

B(1) = 2 //It's either a 0 or a 1.

Now consider the addition of an nth digit. If the nth digit is 0, it may be follow any legal sequence of length (n-1) If the nth digit is 1, then the (n-1)th digit must be a 0. These sequences can all be obtained by taking every sequence of length (n-2) and appending a 0.

Therefore: B(n) = B(n-1) + B(n-2)

$\endgroup$

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.