This lecture introduces permutations, one of the most important concepts in combinatorial analysis.
We first deal with permutations without repetition, also called simple permutations, and then with permutations with repetition.
A permutation without repetition of objects is one of the possible ways of ordering the objects.
A permutation without repetition is also simply called a permutation.
The following subsections give a slightly more formal definition of permutation and deal with the problem of counting the number of possible permutations of objects.
Let , ,..., be objects. Let , , ..., be slots to which the objects can be assigned. A permutation (or permutation without repetition or simple permutation) of , ,..., is one of the possible ways to fill each of the slots with one and only one of the objects (with the proviso that each object can be assigned to only one slot).
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?
An so on, until only one object and one free slot remain.
the order of selection matters (the same objects selected in different orders are regarded as different permutations).
Thus, the difference between simple permutations and permutations with repetition is that objects can be selected only once in the former, while they can be selected more than once in the latter.
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 the objects can be assigned. A permutation with repetition of , ,..., is one of the possible ways to fill each of the slots with one and only one of the objects (with the proviso that an object can be assigned to more than one slot).
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?
There are 5 seats around a table and 5 people to be seated at the table. In how many ways can they seat themselves?
Bob, John, Luke and Tim play a tennis tournament. The rules of the tournament are such that at the end of the tournament a ranking will be made and there will be no ties. How many different rankings can there be?
A byte is a number consisting of 8 digits that can be equal either to 0 or to 1. How many different bytes are there?