Permutations

Chapter

3 videos

AN INTRODUCTION TO ORDERED ARRANGEMENTS

Permutations are a fundamental concept in combinatorics that describe all possible ordered arrangements of elements in a given set. In permutations, all elements are used, and their arrangement is important. Every change in the order of elements creates a different permutation, which distinguishes them from combinations, where order does not matter.

If we have n distinct elements, the number of all possible permutations of these elements is: P(n) = n! (n factorial) where n! = n * (n – 1) * (n – 2) * … * 2 * 1

EXAMPLE 1: BASIC PERMUTATIONS

How many different arrangements of the letters A, B, and C exist? n = 3 → P(3) = 3! = 6 The permutations are: ABC, ACB, BAC, BCA, CAB, CBA.

PERMUTATIONS WITH REPETITION

If a set contains repeating elements, then swapping identical elements does not create a new permutation. In this case, the number of permutations is reduced by dividing by the factorials of the number of repetitions.

If we have n elements, of which:

• r₁ are of the first identical type,
• r₂ are of the second identical type,
• …,
• rₖ are of the k-th identical type,

then the formula is: P(n; r₁, r₂, …, rₖ) = n! / (r₁! * r₂! * … * rₖ!)

EXAMPLE 2: PERMUTATIONS WITH REPEATING ELEMENTS

How many different permutations does the word MAMA have? Letters: M appears 2 times, A appears 2 times → n = 4, r₁ = 2, r₂ = 2 P = 4! / (2! * 2!) = 24 / (2 * 2) = 6 The permutations are: MAMA, MAAM, AMMA, AAMM, AMAM, MMAA.

CIRCULAR PERMUTATIONS

When we arrange elements in a circle, we are dealing with circular permutations. In a circle, rotations of the same arrangement are not considered new permutations.

For n distinct elements in a circle, the formula is: P_circular(n) = (n – 1)!

Example: Arranging 5 people around a table → (5 – 1)! = 4! = 24 possibilities.

CONNECTION TO VARIATIONS AND COMBINATIONS

• Permutations: Uses all elements, order is important.
• Variations: Uses a subset of elements, order is important.
• Combinations: Uses a subset of elements, order is not important.

APPLICATIONS OF PERMUTATIONS

Permutations are used for:

• Arranging people, objects, or characters.
• Coding and creating passwords.
• Rearranging elements without repetition.
• Solving problems in game theory and optimization.

CONCLUSION

Permutations represent all possible ways of ordering elements where the sequence is crucial. The number of permutations grows rapidly with the number of elements. Understanding the different forms of permutations is essential for effectively solving combinatorial problems.

What Are Permutations?

Explanation

Permutations with Repetition

Permutations without Repetition