Counting
The chart below displays the 4 most common types of counting problems:
Order Is Important | Order Is Not Important | |
No Repetition | Permutation Electing Class Officers Choosing r from n can be done in |
Combination Choosing A Committee Choosing r from n can be done in |
Repetition Is Allowed | Permutation with
repetition allowed Character Strings, Words, Bit Strings Choosing r from n can be done in n^{r} ways. |
Combination with
repetition allowed partitioning an integer r as a sum of n nonnegative integers Choosing r from n can be done in |
Here is a discussion about combinations with repetition allowed.
The classic problem here is the number of ways one can express an integer r as a
sum of n nonnegative integers: x_{1} + x_{2} + x_{3}
+ ... + x_{n} = r. For example, with r = 4 and n = 3,
one can write
which can be proven as follows. Imagine a bit string of n-1 zeros and r ones. Think of the zeros are marking the boundaries between piles of ones. The number of ones in the i^{th} pile is x_{i}. Thus every such string of zeros and ones gives rise to some way of writing r as x_{1} + x_{2} + x_{3} + ... + x_{n} . Conversely, every expression of r as x_{1} + x_{2} + x_{3} + ... + x_{n} can be used to design of string of zeros and ones with x_{i} ones in the i^{th} pile defined with zeros as boundary points. So the problem of counting the expressions x_{1} + x_{2} + x_{3} + ... + x_{n} = r is exactly the same problem as counting the bit strings that consist of n-1 zeros and r ones. The number of such strings is much easier to explain: out of the n+r-1 bit string locations, choose n-1 places to put the zeros and put ones in the remaining places. Choosing n-1 places out of n+r-1 is like choosing a committee (we only care what places are chosen, not which one was picked first). The number of ways to do this is C(n+r-1,n-1) [which is the same as C(n+r-1,r)].