The number of binary strings with n zeros and k ones such that no two ones are…

1999

The number of binary strings with n zeros and k ones such that no two ones are adjacent is:

  1. A.

    C(n - 1, k)

  2. B.

    C(n, k)

  3. C.

    C(n, k + 1)

  4. D.

    None of the above

Attempted by 75 students.

Show answer & explanation

Correct answer: D

The correct answer is: None of the above.

First arrange the n zeros in a row:
0 0 0 ... 0

These n zeros create n + 1 gaps where ones can be placed without making two ones adjacent:
- one gap before the first zero
- n - 1 gaps between consecutive zeros
- one gap after the last zero

To form a valid string with k ones, choose k of these n + 1 gaps and place one 1 in each chosen gap.

Number of valid strings = C(n + 1, k).

Since C(n + 1, k) is not listed among the first three options, the answer is None of the above.

Explore the full course: Gate Guidance By Sanchit Sir