Permutations
Lesson · Beginner
Combinatorics: Counting
A permutation is an arrangement of objects in which order matters.
For example, the arrangements
are different permutations of the same three objects.
Factorial
For a positive integer n,
and
For example,
The number of ways to arrange n distinct objects is
For the first position, there are n choices. After one object is used, there are n - 1 choices for the second position, then n - 2, and so on.
Thus,
Suppose we choose and arrange r objects from n distinct objects.
There are
choices for the first position,
for the second, and so on, until r positions have been filled.
Therefore,
or equivalently,
The key idea is:
If some objects are identical, n! counts many arrangements more than once.
If there are n objects in total, with
identical objects of each type, where
then the number of distinct arrangements is
For example, the letters of LEVEL consist of 5 letters, with two L's and two E's.
Thus, the number of distinct arrangements is
Suppose n₁ of the objects are identical.
If we temporarily label these identical objects, every actual arrangement is counted
times, because exchanging their labels does not create a new arrangement.
If there are several groups of identical objects, each actual arrangement is counted
times.
Therefore, the number of distinct arrangements is
In how many ways can 7 different books be arranged on a shelf?
All 7 distinct objects are being arranged.
Therefore,
A race has 10 runners. In how many ways can gold, silver, and bronze medals be awarded?
Order matters because the three medals are different.
There are
choices for gold,
for silver, and
for bronze.
Thus,
How many distinct arrangements of the letters of MISSISSIPPI are possible?
There are 11 letters:
Therefore,
How many six-digit numbers can be formed using each of the digits
exactly once if 1 appears before 2 and 3 appears before 4?
There are
total arrangements.
Exactly half have 1 before 2.
Among those, exactly half have 3 before 4.
Therefore,
How many permutations of
have 1 in an odd-numbered position and 2 in an even-numbered position?
There are 4 odd positions:
and 3 even positions:
Choose the position of 1 in
ways and the position of 2 in
ways.
The remaining 5 numbers can be arranged in
ways.
Thus,
How many 7-digit numbers can be formed using each of
exactly once if the number is greater than 4,000,000?
The first digit must be
So there are
choices for the first digit.
After choosing it, the remaining 6 digits can be arranged freely:
ways.
Therefore,
How many distinct arrangements of
have D appearing before every C?
Without the restriction, the number of arrangements is
Now consider only the relative order of
There are three possible positions for D among these three symbols:
By symmetry, each occurs equally often.
Only
has D before both C's.
Therefore, the desired number is
Five boys and four girls are all distinct. In how many ways can they stand in a row if boys and girls must alternate?
Since there is one more boy than girl, the pattern is forced:
The 5 boys can be arranged in
ways.
The 4 girls can be arranged in
ways.
Therefore,
For a permutation
an inversion is a pair of positions i < j for which
For example, in
the inversions are
Therefore, this permutation has
inversions.
Consider the two permutations
and
Prove that any sequence of swaps that transforms P into Q must contain an odd number of swaps.
We use inversions.
The permutation
has no inversions, so
Now consider
Its inversions are
Therefore,
So P has an even number of inversions, while Q has an odd number.
Now we use the key fact:
Every swap of two elements changes the parity of the number of inversions.
To see why, suppose we swap two elements a and b, with a > b.
Their mutual pair changes its inversion status, contributing a change of 1.
For every element x lying between their positions, the changes involving
either cancel or change the inversion count by 2.
Thus the total change in the number of inversions has the form
which is odd.
Therefore, each swap changes inversion parity:
Since we start with
and must reach
the parity must change an odd number of times.
Hence, any sequence of swaps transforming P into Q must contain an
Selecting A, B, C is the same selection as C, A, B.
If only the selected objects matter and their order does not, a permutation counts each selection multiple times.