## A.7 Permutations and Combinations Suppose we have four balls marked A, B, C, and D in an urn or container, and two balls will he drawn from the urn. To win a lottery, we must pick the balls in the order in which they are drawn. To gain insight into the likelihood of our winning, we should determine how many outcomes are possible. The possible outcomes are: AB AC AD BA BC BD CA CB CD DA DB DC The outcomes AB and BA, for example, are different because we must pick the balls in the correct order. We have listed 12 different outcomes. However, can we be sure that these are all the outcomes? Notice that we arranged the outcomes in four rows and three columns. Each row corresponds to a distinct choice for the first ball; there are four such choices. Once we have made that choice, the second letters in the entries in a row correspond to the remaining distinct choices for the second ball; there are three such choices. The total number of outcomes is therefore  This result can be generalized. For example, if we have four balls and three are drawn, the first ball can be any one of four; once the first ball is drawn, the second ball can be any of three; and once the second ball is drawn, the third ball can be any of two. The number of outcomes is therefore  In general, if we have *n* balls, and we are picking *k* of them, the number of possible outcomes is  This is called the number of permutations of *n* objects taken *k* at a time. If *n* = 4 and *k* = 3, this formula yields  which is the result already obtained. If *n* = 10 and *k* = 5, the formula yields  If *k* = *n*, we are picking all the balls. This is simply called the number of ***permutations*** of *n* objects. The previous formula shows that it is given by  Recall that for a positive integer *n, n*! is defined as the integer times all the positive integers less than it, the value of 0! is defined to be 1, and *n*! is not defined for negative integers. Next consider a lottery that we can win by merely picking the correct balls. That is, we do not have to get the order right. Suppose again that there are four balls marked A, B, C, and D, and two are drawn. Each outcome in this lottery corresponds to two outcomes in the previous lottery. For example, the outcomes AB and BA in the other lottery are both the same for the purposes of this lottery. We will call this outcome A and B. Because two outcomes in the previous lottery correspond to one outcome in this lottery, we can determine how many outcomes there are in this lottery by dividing the number of outcomes in the previous lottery by 2. This means that there are  outcomes in this lottery. The six distinct outcomes are A and B A and C A and D B and C B and D C and D. Suppose now that three balls are drawn from the urn containing the four balls marked A, B, C, and D, and we do not have to get the order right. Then the following outcomes are all the same for the purposes of this lottery: ABC ACB BAC BCA CAB CBA. These outcomes are simply the permutations of three objects. Recall that the number of such permutations is given by 3! = 6. To determine how many distinct outcomes there are in this lottery, we need to divide by 3! the number of distinct outcomes in the lottery, where the order does matter. That is, there are  outcomes in this lottery. They are A and B and C A and B and D A and C and D A and C and D. In general, if there are *n* balls and *k* balls are drawn and the order does not matter, the number of distinct outcomes is given by  This is called the number of ***combinations*** of *n* objects taken *k* at a time. Because  the formula for the number of combinations of *n* objects taken *k* at a time is usually shown as  Using this formula, the number of combinations of eight objects taken three at a time is given by  The ***Binomial theorem***, which is proven in algebra texts, states that for any nonnegative integer *n* and real numbers *a* and *b*,  Because the number of combinations of *n* objects taken *k* at a time is the coefficient of *akbn-k* in this expression, that number is called the ***binomial coefficient***. We will denote it . Example A.10****We show that the number of subsets, including the empty set, of a set containing *n* items is 2*n*. For 0 ≤ *k* ≤ *n*, the number of subsets of size *k* is the number of combinations of *n* objects taken *k* at a time, which is . This means that the total number of subsets is  The second-to-last equality is by the Binomial theorem. ****