We discuss a combinatorial counting technique known as stars and bars. Consider the following problem.
It may be tempting to list every possible combination of non-negative integers in an ordered fashion. However, this method of listing does not work easily for much larger numbers.
Step 1: First, we will create a bijection between solutions to with sequences of length 13 that consist of 10 's and 3 's. What this means is that we want to associate each solution with a unique sequence, and vice versa.
The construction is straightforward. Given a set of 4 integers , we create the sequence that starts with 's, then has a , then has 's, then has a , then has 's, then has a , then has 's. For example, if , then the associated sequence is . Now, if we add the restriction that , the associated sequence will consist of 10 's (from ) and 3 's (from our manual insert), hence have total length 13.
Conversely, given a sequence of length 13 that consists of 10 's and 3 's, set equal to the length of the initial string of 's (before the first ), set equal to the length of the next string of 1's (between the first and second ), set equal to the length of the third string of 's (between the second and third ), and set equal to the length of the last string of 's (after the third ). Then, this yields a solution .
It is clear that the constructions associate a solution with a unique sequence, and vice versa. Hence we have a bijection.
Step 2: Now, it remains to count the number of solutions. Since we have a bijection with the sequences, it is equivalent to count the number of sequences of length 13 that consist of 10 's and 3 's.
First, let us assume that the 's are distinct, say of the form . Then, in a sequence of length 13, there are 13 ways we could place . After which, there are 13-1 ways we could place . After which, there are 13-2 ways we could place . Now, the rest of the sequence have to be 's, and clearly there is only 1 way to do so. By the rule of product, this will yield ways.
However, we have double counted many times, since the 's are actually the same. There are 6 ways ( , ) to arrange the 'distinct' 's. Thus, each actual sequence would have been counted 6 times, so to get the actual number of ways, we will have to divide by 6.
Hence, there are solutions.
Note: Students who are familiar with combinatorics should realize from the above argument that there are solutions.