Permutations and Combinations Show DefinitionsThis topic is an introduction to counting methods used in Discrete Mathematics. Permutations and Combinations involve counting the number of different selections possible from a set of objects given certain restrictions and conditions. We now look to distinguish between permutations and combinations. Definition: A permutation is a selection where the order in which the objects are selected is important and repetition of objects is not allowed. For example the selection ABC is different to the selection ACB as permutations. Definition: A combination is a selection where the order in which the objects are selected is not important and repetition of objects is not allowed. For example, the selection ABC is the same as the selection ACB as combinations. To calculate the number of permutations and combinations we may of course simply list the number the different cases and then simply count the number of different cases. This method becomes tedious though when one is dealing with larger sets of objects. For example, considering the number of combinations of 3 objects selected from a group of 10 distinct objects, this requires 120 different cases which of course will become quite tedious to list. Hence we need to introduce a rigorous and systematic method to solve these counting problems. The Fundamental Counting PrincipleThis principle is called so due to its importance to counting theory. In essence, this principle states that; If there are distinct ways to do , andq distinct ways to do , then in total there are ways to do both and provided and are independent. Simply stated, this states that when considering two events, both mutually exclusive (independent), then the total number of ways to do both events is the number of ways to do the first, multiplied by the number of ways to do the second. This principle may also be extended to several differing events as well. Consider the example below.
The next example shows a problem where the cases being considered are not independent, however the fundamental counting principle may be applied.
Permutations and the Factorial NotationThe product of all the positive integers less than or equal to a number, say, is denoted by and is read “ factorial”. That is, So as simple examples we have, where By definition, we have that; The factorial function , has domain equal to the non-negative integers. (Although in higher undergraduate mathematics there turns out to be a way to consider the factorial function for negative integers and fractional values). This notation is particularly handy when considering arrangements in lines or circles. Consider the example below.
In general when arranging distinct objects in a row (repetitions not allowed) we have that the number of arrangements or permutations of those objects are given by . Now, if we were to have objects, not all distinct, then this is a different matter, and in fact there does exist a formula for such a case. The formula is given below. If there are objects, with objects being non-distinct and of a certain type and objects being non-distinct and of another type and objects being non-distinct and of another type and so on, we have that the number of arrangements of such objects in a row is given by, Although this may not be immediately obvious, the reason for the division by the values of and is simply to eliminate all the rearrangements of the similar objects between themselves. Consider the example below that illustrates the use of this formula.
Suppose now that we wish to arrange objects in a circle. The difference between this and the above case is the lack of a defined starting point and a defined ending point. Because of this we must assign one of the objects being arranged, to be our reference point and it is then that we may arrange the remaining objects about the object chosen to be the reference point. Hence upon removing an object (to place as a reference point) from the total objects to be arranged, we end up with one less object and then these objects must be arranged in the same way as was considered in example 2. Hence we have that; If there are objects, all distinct, then the total number of ways in which these objects may be arranged about a circle is given by .
Suppose now that we have objects among those being similar and another being similar and so on. The number of arrangements about a circle is now given by the total number of arrangements divided by the arrangements of the similar objects themselves. Hence we have that; If there are objects with similar and another similar and another similar etc. it follows that the total number of arrangements of those objects in a circle is given by We now consider the arrangements of objects on a necklace, or a keychain. Suppose that we such to arrange distinct beads on a necklace. The total number of arrangements is given by the total number of unrestricted arrangements in a circle divided by . The division by is due to the symmetry of the necklace by being able to turn the necklace around and observe the exact same permutation. Hence we have that; Given objects, each distinct, the number of arrangements of these objects on a necklace is given by, We have so far considered arrangements in rows and circles, given similarity between some of the objects. We shall now consider the number of arrangements of objects given certain conditions. Recall that a permutation of an object is simply an ordered selection or an arrangement. We thus have that, The number of permutations of objects choosing at a time is given by; Notice that for the formula becomes, Thus, if one is choosing all the objects in the set then the total number of permutations is simply the same as arranging all the objects into a line which should at this point be quite obvious. Also, this formula assumes that no repetitions are allowed. Let us consider an example to illustrate this formula’s use.
We are now going to consider some examples of questions that involve permutations given certain conditions. Students tend to have difficulty in grasping the techniques involved, since every question must be tackled on its own merits. The best way to master such questions is to expose oneself to as many examples as possible.
Note: Do not fall into the common trap of listing cases and then counting the possible arrangements in each case. This is futile and tedious. If possible always look to the complementary event first.
The next example involves repetitions.
We shall now consider a probability question involving permutations. Recall that the probability of an event is given by where the sample space is the set of all possible outcomes.
CombinationsRecall that a combination is a selection where the order of the objects is not important. The number of combinations of objects, all distinct, taken at a time is given by, and is read “ choose ”. A popular alternative notation for this is, We shall now consider some examples that illustrate the use of this formula.
Questions involving combinations may imply restrictions upon the possible selections made. We will consider some examples to illustrate some possible types of questions.
Note: Students often ask when to multiply results and when to add them (For e.g. in the above example we multiplied them). As a general rule, results are added if the conjunction between the two events is an “and”, and the results are added if the conjunction between the events is an “or”. Consider the example below for an “or” example.
We shall now consider some examples involving both combinations and permutations. With these examples, at times the fundamental counting principle may be used to great success. However, the fundamental counting principle is not necessarily the easiest way to solve each problem. Observe the examples below. Again, the best way to master these problems is to solve a lot of them. Also, from here on in and for all examination type questions, students should be wary about repetitions. Students should always ask themselves if repetition is allowed or not. Often this is easily answered, however students should still practice distinguishing between the two.
|