Quantitative Aptitude > Permutations and Combinations
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 timeconsuming, 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 fivedigit 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 3person 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

