GATE CS 1999 Q1.3 — Combinatorics: Counting, Recurrence Relations, Generating Functions

We want to find the number of binary strings containing $n$ zeros and $k$ ones such that no two ones are adjacent.

We can solve this using the gap method:

1. First, arrange the $n$ zeros in a line. This creates $n + 1$ available slots (gaps) where the ones can be placed (one slot before the first zero, $n-1$ slots between the zeros, and one slot after the last zero):
   $$\_ \; 0 \; \_ \; 0 \; \_ \; \dots \; \_ \; 0 \; \_$$
2. To ensure that no two ones are adjacent, we must place at most one '1' in any of these $n + 1$ gaps.
3. Since we have $k$ ones to place, we need to choose $k$ distinct gaps out of the $n + 1$ available gaps.

The number of ways to choose $k$ gaps from $n + 1$ is given by the binomial coefficient:

Comparing this with the given options:

• A: $^{n-1}C_k$ (Incorrect)
• B: $^nC_k$ (Incorrect)
• C: $^nC_{k+1}$ (Incorrect)

Therefore, the correct option is D (None of the above).