Permutations

Definition and Basic Concepts

Permutation

Permutation: an ordered arrangement of objects. Order: crucial factor distinguishing permutations from combinations. Elements: distinct or identical. Total permutations depend on object count and repetition.

Set and Sequence

Set: collection of distinct elements, unordered. Sequence: ordered list. Permutations: sequences formed from set elements.

Importance in Combinatorics

Permutations: foundation of counting problems, probability, algebra, and discrete structures. Essential for arrangement, ranking, and ordering scenarios.

Factorial Function

Definition

Factorial (n!): product of all positive integers ≤ n. Formula: n! = n × (n−1) × ... × 2 × 1.

Properties

Special case: 0! = 1 by convention. Growth: factorial grows faster than exponential functions. Useful in permutations and combinations calculations.

Examples

Examples: 5! = 120, 3! = 6, 7! = 5040.

n! = { 1, if n = 0 n × (n-1)!, if n > 0}

Permutations Without Repetition

Concept

Selection and arrangement of r elements from n distinct elements without reuse. Order matters.

Formula

Number of permutations: P(n, r) = n! / (n-r)!.

Example

Arrange 3 letters from A, B, C, D: P(4,3) = 4! / (4-3)! = 24.

Permutations With Repetition

Concept

Permutations where elements may repeat. Objects can be identical or repeats allowed.

Multiset Permutations

For multiset with n total items and duplicates of counts n1, n2,..., nk, permutations count: n! / (n1! × n2! × ... × nk!).

Example

Permutations of letters in "BANANA": total letters 6, with A=3, N=2, B=1.

P = 6! / (3! × 2! × 1!) = 720 / (6 × 2) = 60

Circular Permutations

Definition

Arrangements around a circle where rotations are equivalent. Order matters, but starting point is not distinguished.

Formula

Number of circular permutations of n distinct elements: (n-1)!.

Example

Seating 5 people around a round table: (5-1)! = 4! = 24 arrangements.

Formulas and Notation

Permutation Notation

Common notation: P(n, r), nPr, or $_nP_r$ for permutations of r elements from n.

Summary of Key Formulas

Factorial Identities

n! = n × (n-1)!P(n,r) = n! / (n-r)!0! = 1(n-r)! = product of integers from 1 to (n-r)

Permutation Algorithms

Lexicographic Ordering

Algorithm: generate permutations in dictionary order. Steps: find pivot, swap, reverse suffix.

Heap's Algorithm

Efficient generation of all permutations. Recursive and iterative versions. Minimizes swaps.

Steinhaus–Johnson–Trotter

Generates permutations by adjacent swaps. Produces permutations with minimal change between steps.

// Pseudocode for next lexicographic permutation:1. Find largest index i with a[i] < a[i+1]2. Find largest index j > i with a[j] > a[i]3. Swap a[i], a[j]4. Reverse a[i+1..end]

Applications

Probability

Permutations used to calculate event arrangements and sample spaces.

Cryptography

Permutation ciphers rely on rearrangement of letters or bits.

Scheduling

Task or resource ordering based on permutations to optimize sequences.

Group Theory

Permutations form symmetric groups; key in abstract algebra.

Relation to Combinations

Difference

Combinations: order irrelevant. Permutations: order matters.

Formula Connection

P(n,r) = C(n,r) × r!, where C(n,r) = n! / (r!(n-r)!).

Interpretation

Permutations = ways to select and arrange r elements. Combinations = ways to select r elements only.

Counting Principles

Multiplication Principle

Total arrangements = product of choices at each step.

Addition Principle

Applicable when events are mutually exclusive; sum of counts.

Inclusion-Exclusion

Used for counting permutations with restrictions or overlaps.

Examples and Exercises

Example 1

Number of ways to arrange 4 books on a shelf: 4! = 24.

Example 2

Number of distinct permutations of "LEVEL": letters L=2, E=2, V=1.

5! / (2! × 2! × 1!) = 120 / 4 = 30

Exercise

Calculate permutations of 5 elements taken 3 at a time.

Solution

P(5,3) = 5!/(5-3)! = 5 × 4 × 3 = 60.

Common Misconceptions

Order Irrelevance

Error: treating permutations as combinations. Correction: permutations require order consideration.

Repetition Confusion

Error: ignoring element repetition effects. Correction: use multiset formula or repetition formulas appropriately.

Circular Permutations

Error: counting rotations as distinct. Correction: subtract rotational equivalences.

References

• R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, 1994, pp. 125-170.
• J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001, pp. 12-50.
• R. P. Stanley, Enumerative Combinatorics, Volume 1, Cambridge University Press, 2011, pp. 21-65.
• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, pp. 40-75.
• M. Aigner, Discrete Mathematics, Springer, 2007, pp. 90-130.