This lecture introduces -permutations, a basic concept in combinatorial analysis. Before reading this lecture, you should read the lecture on permutations.
We first deal with -permutations without repetition and then with -permutations with repetition.
A -permutation without repetition of objects is a way of selecting objects from a list of . The selection rules are:
the order of selection matters (the same objects selected in different orders are regarded as different -permutations);
each object can be selected only once.
A -permutation without repetition is also simply called -permutation.
The following subsections give a slightly more formal definition of -permutation and deal with the problem of counting the number of possible -permutations.
Let , ,..., be objects. Let , , ..., be () slots to which of the objects can be assigned. A -permutation (or -permutation without repetition or simple -permutation) of objects from , ,..., is one of the possible ways to choose of the objects and fill each of the slots with one and only one object. Each object can be chosen only once.
Example Consider three objects , and . There are two slots ( and ) to which we can assign two of the three objects. There are six possible -permutations of the three objects (six possible ways to choose two objects and fill the two slots with the two objects):
Denote by the number of possible -permutations of objects. How much is in general? In other words, how do we count the number of possible -permutations of objects?
We can derive a general formula for by filling the slots in a sequential manner:
First, we assign an object to the first slot. There are objects that can be assigned to the first slot, so there are
Then, we assign an object to the second slot. There were objects, but one has already been assigned to a slot. So, we are left with objects that can be assigned to the second slot. Thus, there areand
Then, we assign an object to the third slot. There were objects, but two have already been assigned to a slot. So, we are left with objects that can be assigned to the third slot. Thus, there areand
An so on, until we are left with objects and only one free slot (the -th).
Finally, when only one free slot remains, we assign one of the remaining objects to it. Thus, there areand
Therefore, by the above sequential argument, the total number of possible -permutations of objects is
can be written as
Remembering the definition of factorial, we can see that the numerator of the above ratio is while the denominator is , so the number of possible -permutations of objects is
The number is usually indicated as follows:
Example The number of possible -permutations of objects is
A -permutation with repetition of objects is a way of selecting objects from a list of . The selection rules are:
the order of selection matters (the same objects selected in different orders are regarded as different -permutations);
each object can be selected more than once.
Thus, the difference between -permutations without repetition and -permutations with repetition is that objects can be selected more than once in the latter, while they can be selected only once in the former.
The following subsections give a slightly more formal definition of -permutation with repetition and deal with the problem of counting the number of possible -permutations with repetition.
Let , ,..., be objects. Let , , ..., be () slots to which of the objects can be assigned. A -permutation with repetition of objects from , ,..., is one of the possible ways to choose of the objects and fill each of the slots with one and only one object. Each object can be chosen more than once.
Example Consider three objects , and and two slots ( and ). There are nine possible -permutations with repetition of the three objects (nine possible ways to choose two objects and fill the two slots with the two objects, being allowed to pick the same object more than once):
Denote by the number of possible -permutations with repetition of objects. How much is in general? In other words, how do we count the number of possible -permutations with repetition of objects?
We can derive a general formula for by filling the slots in a sequential manner:
First, we assign an object to the first slot. There are objects that can be assigned to the first slot, so there are
Then, we assign an object to the second slot. Even if one object has been assigned to a slot in the previous step, we can still choose among objects, because we are allowed to choose an object more than once. So, there are objects that can be assigned to the second slot andand
Then, we assign an object to the third slot. Even if two objects have been assigned to a slot in the previous two steps, we can still choose among objects, because we are allowed to choose an object more than once. So, there are objects that can be assigned to the second slot andand
An so on, until we are left with only one free slot (the -th).
When only one free slot remains, we assign one of the objects to it. Thus, there are:and
Therefore, by the above sequential argument, the total number of possible -permutations with repetition of objects is
Example The number of possible -permutations of objects is
Below you can find some exercises with explained solutions.
There is a basket of fruit containing an apple, a banana and an orange and there are five girls who want to eat one fruit. How many ways are there to give three of the five girls one fruit each and leave two of them without a fruit to eat?
Giving the 3 fruits to 3 of the 5 girls is a sequential problem. We first give the apple to one of the girls. There are 5 possible ways to do this. Then we give the banana to one of the remaining girls. There are 4 possible ways to do this, because one girl has already been given a fruit. Finally, we give the orange to one of the remaining girls. There are 3 possible ways to do this, because 2 girls have already been given a fruit. Summing up, the number of ways to assign the three fruits is equal to the number of 3-permutations of 5 objects (without repetition). If we denote it by , then
An hexadecimal number is a number whose digits can take sixteen different values: either one of the ten numbers from 0 to 9, or one of the six letters from A to F. How many different 8-digit hexadecimal numbers are there, if an hexadecimal number is allowed to begin with any number of zeros?
Choosing the 8 digits of the hexadecimal number is a sequential problem. There are 16 possible ways to choose the first digit and 16 possible ways to choose the second digit. So, there are 16x16 possible ways to choose the first two digits. There are 16 possible ways two choose the third digit and 16x16 possible ways to choose the first two. Thus, there are 16x16x16 possible ways to choose the first three digits. An so on, until we have chosen all digits. Therefore, the number of ways to choose the 8 digits is equal to the number of 8-permutations with repetition of 16 objects:
An urn contains ten balls, each representing one of the ten numbers from 0 to 9. Three balls are drawn at random from the urn and the corresponding numbers are written down to form a 3-digit number, writing down the digits from left to right in the order in which they have been extracted. When a ball is drawn from the urn it is set aside, so that it cannot be extracted again. If one were to write down all the 3-digit numbers that could possibly be formed, how many would they be?
The 3 balls are drawn sequentially. At the first draw there are 10 balls, hence 10 possible values for the first digit of our 3-digit number. At the second draw there are 9 balls left, hence 9 possible values for the second digit of our 3-digit number. At the third and last draw there are 8 balls left, hence 8 possible values for the third digit of our 3-digit number. In summary, the number of possible 3-digit numbers is equal to the number of 3-permutations of 10 objects (without repetition). If we denote it by , then
Most of the learning materials found on this website are now available in a traditional textbook format.