Teacher resources and professional development across the curriculum
Teacher professional development and classroom resources across the curriculum
We can solve the problem of the flavors by a different method that will give us a broader understanding of the subsets than the bijection method provided. Specifically, we need a strategy that not only reveals the total number of subsets, but that is also capable of categorizing the subsets by size. This is a common theme in mathematics; solving problems in different ways deepens our understanding of what is really happening. To re-phrase our problem, we are seeking a formula that will tell us how many subsets of a given size can be made from the original set of six flavors. We would then like to generalize this formula to tell us how many subsets of size k, called k-subsets, can be made of a set of n elements. In doing this, we will have to use the important combinatorial concepts of permutation and combination.
We can start our thought process by considering how many ways the six flavors can be arranged if we count each unique ordering separately. (Remember that previously we gave no significance to order and considered, for example, the subsets AB and BA to be the same.) Arrangements such as these, in which order matters, are known as permutations. We can imagine the possible permutations of six flavors as a sequence of six empty slots.
Notice that there are six possible flavors that can occupy the first slot, five that can occupy the second, four for the third, and so on. This is because once a specific flavor is used, we don't want it to appear again in the same permutation. The total number of permutations of six flavors is then 6 × 5 × 4 × 3 × 2 × 1 = 720, which we denote as 6!, called "six factorial." In general, the number of permutations of n objects will be n! As a shorthand, we can write P(n,n), or "the permutations of n objects taken n at a time."
So, permutations have a simple formula in terms of the factorial, but there is more to consider. Remember, we also want to be able to find the number of arrangements involving fewer than all six of the elements—what we call subsets. Furthermore, in the final analysis we are not concerned with the order of flavors; we really don't care if a subset has salty before sweet or sweet before salty. Such arrangements, in which order does not matter, are known as combinations. To find a formula for counting combinations of a given size, we will have to deal with both of these considerations.
First, let's figure out how to deal with finding smaller arrangements selected from a pool of six objects in which order still matters. For example, to find the number of ways to order two flavors out of the set of six, we can imagine two slots, the first of which has six possible flavors, the second of which has only five possible flavors, once a flavor has "filled" the first slot. After multiplying, as we did before, we see that there are thirty possible ways to order two out of the six flavors. In the language of combinatorics, we say that we have found the number of permutations of six objects taken two at a time. We can write P(6,2) to express this; the general form for this expression is P(n,k), or "the permutations of n objects taken k at a time."
Notice that P(6,2) is less than P(6,6). Why is this? P(6,6) gives the total number of unique orderings of all six flavors, but to find P(6,2), we are concerned with only two flavors. Going back to the six–slot concept from before, we can let the two flavors we care about occupy the first two slots. For example:
A B _ _ _ _
The remaining four slots can be ordered in 4! (24) ways, all of which have the same first two flavors. So, P(6,6) over-counts P(6,2) by a factor of twenty-four. Therefore, to find P(6,2), we should divide P(6,6) by 4!. Recognizing that 4 = (6-2), we can write the following expression for the value of P(6,2):
We can then generalize this for P(n,k):
This is the formula for the number of permutations of n objects taken k at a time.
Having addressed the first of our concerns—counting smaller permutations— we can move on to the question of what to do about order. Permutations, recall, count each unique ordering of objects separately, but in the problem of the flavors, we don't really care about the order of flavors in a subset. Knowing that P(n,k) gives the number of permutations of n objects taken k at a time, can we use this to determine the number of combinations in a subset of permutations? If so, we could then find the number of combinations of six, five, four, three, two, and single flavors. Then, after adding these together, we will have found the total number of subsets of six flavors.
We can start by realizing that the number of permutations will always be greater than the number of combinations. For example, P(n,k) treats the arrangements ABC, ACB, BCA, BAC, CAB, and CBA as different. Viewing them as combinations of three flavors, however, we would consider them all to be the same combination. So, P(n,k) must be over-counting if we are interested only in combinations. By what factor does P(n,k) over-count?
P(n,k) over-counts by the number of ways to arrange k objects. This is evident in the example of six permutations of three objects taken three at a time above. If we divide the six objects by 3!, or six, we get one, which is the number of combinations of three objects, taken three at a time. In general, will tell us the number of combinations of n objects taken k at a time. We call this C(n,k). Using the formula for P(n,k) from above and recognizing that P(k,k) = k!, we can write:
For example, C(10,3) represents the number of possible three-topping pizzas that we could choose given a total of ten possible toppings.
Using this notation, we can complete the following short chart to solve the original problem of the flavors by enumerating the subsets according to their size.
Adding the results for the number of subsets of size one, two, three, four, five, and six elements, we get:
6 + 15 + 20 + 15 + 6 + 1 = 63
Although it took us a while to derive the formula for C(n,k), using it to count k-subsets in this manner is much faster than listing them all.
We have now efficiently answered the problem of the flavors in two different ways, and we can see that adding together all the possible values of C(n,k), as k ranges from 1 through 6, yields the same value that we found in our previous solution using bijection. Furthermore, we can imagine that each of the specific k-subsets corresponds to a unique binary string. In our next section, we will use a similar method to derive what is going on at the heart of one of the most famous and fascinating number patterns in mathematics: Pascal's Triangle.
Next: 2.4 Pascal's Triangle