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:
- A.
C(n - 1, k)
- B.
C(n, k)
- C.
C(n, k + 1)
- 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.