Permutations Of Pi Objects - Class Notes

Permutations of n objects A set is just a group of objects and that the order in which the objects are listed is irrelevant. We now consider the number of different ways all the objects   are listed is irrelevant. Consider the number of different ways all the objects in a set may be arranged in order. A set containing n distinguishable objects has   n! different orderings of the objects belonging to the set. We can see this by thinking in terms of having n slots to fill with the n objects in the set. Each slot can hold one object,   so we can choose an object for the first slot in n ways; there are then n-1 objects available for the second slot, so we can select an object for the second slot in n-1 ways,   leaving n-2 objects available for the third slot, until the last remaining object has to   be placed in the final slot. We say that there are n! distinct arrangements (technically, we call each arrangement or ordering a permutation) of the n objects in the   set. Permutations of n objects taken r at a time Suppose we have a set containing n objects, and that we have r (or n) slots to fill. In how many ways can we do this, assuming that each object is "used up" once it is allocated to a slot? We number the slots 1 to r and fill each in turn. We can choose any of n objects to fill   the first slot. Having filled the first slot, there are n-1 objects available, any of which may be chosen for the second slot. Therefore, the first two slots can be filled in n(n-1) ways.   First three slots can be filled in n(n-1)(n-2) ways. By the time we have filled (r-1)st slot and are ready for the rth slot, we have used r-1 members of our set and therefore have n-(r-1)=n-r+1 members left to choose from. Hence, the r slots can be filled in n(n-1)x...x(n-r+1)   / (n-r)! ways. Thus there are (n) ways of ordering r elements taken from a set containing n elements and arranging them. We are here involved in two processes, choosing r objects and arranging them. The number of ways of choosing r objects out of n distinguishable objects is called the number of permutations of n objects taken r at a time and is denoted by (n)r ('n permution   r') (n)r = (n)/(n-r)! = n!/(n-r)! This formula is also valid for r = n, if we adopt the convention that 0! = 1. Combinations of n objects taken r at a time. Now we want to count the number of ways of choosing r elements out of the n elements in our set without regard to the arrangement of the chosen elements.   [We want to determine the number of r-element subsets that we can form.] We denote this by (n)r ('n combination r') When we found the number of permutations of n objects taken r at a time, we divided the process into two operations - choosing r objects and then arranging them. We are now only interested in the first operation.   A little reflection will convince you that there are therefore r! times more permutations than combinations. (n)r = (n)/(n-r)! = n!/(n-r)! Permutations, with repetitions. Now we have n types of objects and r slots, and that we have at least r objects of each type available. We can thus fill the first slot with any of the n types of objects; there are still n types of objects available for the second slot because there are at least r objects of each type.   Thus, there are still n types of objects available for the final, rth slot. Thus the number of permutations of n types of objects taken r at a time, allowing repetitions   is