Lesson 6

Now let us use the idea of dividers to solve the previous three problems. In the first problem, we need to find the number of ways to break the number \(n\) into positive summands. We already know that the number of ways to break it into \(k\) summands will be \(\binom{n-1}{k-1}\). Therefore, the total number of ways will be \[\sum_{k=1}^{n}\binom{n-1}{k-1}= \sum_{k=0}^{n-1}\binom{n-1}{k}=2^{n-1}\ .\] But this can be immediately seen: breaking into summands is equivalent to choosing positions for dividers in the \(n-1\) available spaces.

In the second problem, we need to count the number of strings of \(m\) zeros and \(n\) ones, in which no two ones are adjacent. First, we place the \(m\) zeros. This creates \(m+1\) spaces for ones (to the left of all zeros, in all gaps, and to the right of all zeros). We need to place at most one one in each of these spaces. Thus, the answer will be \(\binom{m+1}{n}\).

Finally, in the third problem, we need to find the number of ways to choose \(k\) books from \(n\) books placed in a row, such that no two books are adjacent. This problem easily reduces to the previous one: write zeros on the books we do not take, and ones on the books we take; this will create a sequence with \(k\) ones, in which no two ones are adjacent.