Quantitative Aptitude > Permutations and Combinations

Add Comment Bookmark share + Refresher Material


Multiplication Principle

  • Suppose there are two choices to be made sequentially and that the second choice is independent of the first choice. Suppose also that there are k different possibilities for the first choice and m different possibilities for the second choice. The multiplication principle states that under those conditions, there are km different possibilities for the pair of choices.

    For e.g. suppose that a meal is to be ordered from a restaurant menu and that the meal consists of one entre´e and one dessert. If there are  entre´es and  desserts on the menu, then there are  different meals that can be ordered from the menu.

  • The multiplication principle applies in more complicated situations as well. If there are more than two independent choices to be made, then the number of different possible outcomes of all of the choices is the product of the numbers of possibilities for each choice.

    Ex.  Suppose that a computer password consists of four characters such that the first character is one of the 10 digits from 0 to 9 and each of the next 3 characters is any one of the uppercase letters from the 26 letters of the English alphabet. How many different passwords are possible?

    Sol.  The description of the password allows repetitions of letters. Thus, there are  possible choices for the first character in the password and  possible choices for each of the next  characters in the password. Therefore, applying the multiplication principle, the number of possible passwords is .

    Note that if repetitions of letters are not allowed in the password, then the choices are not all independent, but a modification of the multiplication principle can still be applied. There are  possible choices for the first character in the password,  possible choices for the second character,  for the third character because the first letter cannot be repeated, and  for the fourth character because the first two letters cannot be repeated. Therefore, the number of possible passwords is .

    Ex.  Each time a coin is tossed, there are  possible outcomes—either it lands heads up or it lands tails up. Using this fact and the multiplication principle, you can conclude that if a coin is tossed  times, there are possible outcomes.

Counting Methods - Permutations and Factorials

  • Suppose you want to determine the number of different ways the  letters  and  can be placed in order from  to . The following is a list of all the possible orders in which the letters can be placed.

    There are 6 possible orders for the 3 letters.

    Now suppose you want to determine the number of different ways the  letters  and  can be placed in order from  to . Listing all of the orders for  letters is time-consuming, so it would be useful to be able to count the possible orders without listing them. To order the  letters, one of the  letters must be placed first, one of the remaining  letters must be placed second, one of the remaining  letters must be placed third, and the last remaining letter must be placed fourth. Therefore, applying the multiplication principle, there are  ways to order the  letters.

  • More generally, suppose  objects are to be ordered from , and we want to count the number of ways the objects can be ordered. There are  choices for the first object,  choices for the second object,  choices for the third object, and so on, until there is only  choice for the  object. Thus, applying the multiplication principle, the number of ways to order the  objects is equal to the product

    Each order is called a permutation, and the product above is called the number of permutations of  objects.

    Because products of the form  occur frequently when counting objects, a special symbol , called  factorial, is used to denote this product. For e.g.

    As a special definition, .

    Note that  and so on. 

    Ex.  Suppose that 10 students are going on a bus trip, and each of the students will be assigned to one of the 10 available seats. Then the number of possible different seating arrangements of the students on the bus is

    Now suppose you want to determine the number of ways in which you can select  of the  letters  and and place them in order from to. Reasoning as in the preceding examples, you find that there are or, ways to select and order them.

  • More generally, suppose that  objects will be selected from a set of  objects, where  and the  objects will be placed in order from  to . Then there are  choices for the first object, choices for the second object,  choices for the third object, and so on, until there are  choices for the th object. Thus, applying the multiplication principle, the number of ways to select and order  objects from a set of  objects is . It is useful to note that

    This expression represents the number of permutations of  objects taken  at a time; that is, the number of ways to select and order  objects out of  objects.

    Ex.  How many different five-digit positive integers can be formed using the digits  and if none of the digits can occur more than once in the integer?

    Sol. This example asks how many ways there are to order  integers chosen from a set of integers. According to the counting principle above, there are  ways to do this. Note that this is equal to

Counting Methods - Combinations

  • Given the five letters A, B, C, D, and E, suppose that you want to determine the number of ways in which you can select 3 of the 5 letters, but unlike before, you do not want to count different orders for the 3 letters. The following is a list of all of the ways in which 3 of the 5 letters can be selected without regard to the order of the letters.

    There are 10 ways of selecting the 3 letters without order. There is a relationship between selecting with order and selecting without order. The number of ways to select 3 of the 5 letters without order, which is 10, multiplied by the number of ways to order the 3 letters, which is 3!, or 6, is equal to the number of ways to select 3 of the 5 letters and order them, which is . In short,

    This relationship can also be described as follows.

  • More generally, suppose that  objects will be chosen from a set of  objects, where , but that the  objects will not be put in order. The number of ways in which this can be done is  called the number of combinations of  objects taken  at a time and is given by the formula   . Another way to refer to the number of combinations of n objects taken k at a time is  choose , and two notations commonly used to denote this number are  and

    Ex.  Suppose you want to select a 3-person committee from a group of 9 students. How many ways are there to do this?

    Sol.  Since the 3 students on the committee are not ordered, you can use the formula for the combination of 9 objects taken 3 at a time, or "9 choose 3":

    Using the terminology of sets, given a set  consisting of  elements,  choose  is simply the number of subsets of  that consist of  elements. The formula  also holds when  and .

     choose  is  , which corresponds to the fact that there is only one subset of  with 0 elements, namely the empty set.

     choose  is , since there is only one subset of  with  elements, namely the set  itself.

  • Finally, note that  choose  is always equal to  choose, because

     

Comments Add Comment
Ask a Question