Prove that the number of ways of arranging $p$ $1's$ and $q$ $0's$ in a line such that no two $1's$ are adjacent is ${q+1 \choose p}.$

Question

If we can prove that the total number of ways will be ${q \choose p} + {q \choose p-1}$. It will suffice. Again, I don't know if $p > q$ or the other way around.

Answer 1

Line up the $q$ zeros in a row. This creates $q + 1$ spaces, $q - 1$ between successive zeros and two at the ends of the row. For instance, if there are ten zeros, we have eleven spaces. $$\square 0 \square 0 \square 0 \square 0 \square 0 \square 0 \square 0 \square 0 \square 0 \square 0 \square$$ To separate the $p$ ones, we must choose $p$ of these $q + 1$ spaces in which to place a $1$.

Note that if $p > q + 1$, the task is impossible since at least two ones must be adjacent. However, the result still holds since $\binom{q + 1}{p} = 0$ if $p > q + 1$.

Answer 2

Hint: each $1$ is either in the last position or is followed by a $0$.