2.1 Permutations without repetition

Permutations Without Repetition

Permutations without repetition count the number of ways to arrange distinct items in a specific order, where each item can only be used once. This is one of the most fundamental tools in combinatorics, and it shows up constantly in probability, algorithm analysis, and any problem where the order of a selection matters.

Permutations and Their Characteristics

Definition and Key Features

A permutation is an ordered arrangement of distinct objects, where each object appears at most once. Two things make a permutation what it is:

• Order matters. The arrangement ABC is different from BAC.
• No repetition. Once you place an object, it's used up.

This is what separates permutations from combinations, where only the selection matters and order is irrelevant. Choosing players A, B, C for a team is a combination; lining them up first, second, third is a permutation.

The number of permutations depends on two things: how many total objects you have ($n$) and how many positions you're filling ($r$).

Applications in Combinatorics

Permutations are a building block for many other counting problems:

• Probability: Calculating the likelihood of ordered outcomes (e.g., the exact finishing order in a race)
• Advanced counting: Concepts like derangements (permutations where no object stays in its original position) and circular permutations build directly on this foundation
• Algorithm analysis: Sorting algorithms like quicksort and heapsort are analyzed by considering how many permutations of input data are possible

Calculating Permutations Using Factorials

Understanding Factorial Notation

The factorial of a non-negative integer $n$, written $n!$, is the product of all positive integers from 1 up to $n$:

$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$

A few key facts:

• $0! = 1$ by convention. This isn't intuitive, but it makes formulas work correctly (there's exactly one way to arrange zero objects: do nothing).
• Factorials grow fast. $5! = 120$, $10! = 3{,}628{,}800$, and $20!$ is already over $2.4 \times 10^{18}$.
• For very large $n$, Stirling's approximation gives a useful estimate: $n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$

Permutations and Factorial Calculations

Arranging all $n$ objects: The number of ways to arrange $n$ distinct objects into $n$ positions is simply $n!$. For the first position you have $n$ choices, then $n-1$ for the second, then $n-2$, and so on.

Arranging $r$ objects out of $n$: When you're only filling $r$ positions from $n$ available objects, use the formula:

$P(n,r) = \frac{n!}{(n-r)!}$

Here's how to apply it step by step:

1. Identify $n$ (total distinct objects) and $r$ (number of positions to fill).
2. Compute $n!$ and $(n-r)!$.
3. Divide: $P(n,r) = \frac{n!}{(n-r)!}$.

Example: How many ways can you award gold, silver, and bronze medals to 3 of 8 runners?

• $n = 8$, $r = 3$
• $P(8,3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336$

Notice that the $(n-r)!$ in the denominator cancels out the tail end of $n!$, leaving you with just the first $r$ terms multiplied together. That's why $P(n,r) = n \times (n-1) \times \cdots \times (n-r+1)$, which has exactly $r$ factors.

Fundamental Counting Principle for Permutations

Understanding the Principle

The Fundamental Counting Principle (also called the multiplication principle) says: if one event can occur in $m$ ways and a second independent event can occur in $n$ ways, then the two events together can occur in $m \times n$ ways. This extends to any number of sequential events.

This principle is actually why the factorial formula works. When you arrange $n$ objects:

• Position 1: $n$ choices
• Position 2: $n - 1$ choices
• Position 3: $n - 2$ choices
• ...and so on

Multiplying all these together gives $n \times (n-1) \times (n-2) \times \cdots \times 1 = n!$

Applying the Principle to Permutations

The counting principle is especially useful when a problem has restrictions, because the factorial formula alone won't handle special conditions.

Example: How many ways can 5 people sit in a row if Person A must sit in the middle seat?

1. Place Person A in the middle seat: 1 way (forced).
2. Fill the remaining 4 seats with 4 people: $4! = 24$ ways.
3. Total: $1 \times 24 = 24$ arrangements.

Example: How many 3-letter "words" can you form from the letters A, B, C, D, E if no letter repeats?

1. First letter: 5 choices.
2. Second letter: 4 choices.
3. Third letter: 3 choices.
4. Total: $5 \times 4 \times 3 = 60$, which matches $P(5,3) = 60$.

For problems with constraints like "these two items can't be adjacent" or "this item must come before that one," break the problem into stages using the counting principle, handling the most restrictive condition first.

Permutations in Real-World Scenarios

Applications in Various Fields

• Scheduling: Ordering tasks in a manufacturing process or project timeline where sequence matters and no task repeats.
• Cryptography: Substitution ciphers work by permuting the alphabet. A simple substitution cipher over 26 letters has $26!$ (roughly $4 \times 10^{26}$) possible keys.
• Sports: Determining the number of possible finishing orders in a race, or structuring round-robin tournament matchups.
• Biology: Analyzing possible orderings of nucleotide bases in a DNA segment, or studying protein folding sequences.
• Computer science: Evaluating sorting algorithm performance by considering how many input permutations an algorithm must handle.

Problem-Solving Strategies

When you encounter a permutation problem, a consistent approach helps:

1. Determine if order matters. If rearranging the same items gives a different outcome, you're dealing with permutations.
2. Check for repetition. If each item can only be used once, it's a permutation without repetition.
3. Identify $n$ and $r$. What's the total pool of objects? How many positions are you filling?
4. Look for restrictions. If there are special conditions, use the counting principle stage by stage rather than plugging straight into $P(n,r)$.
5. Compute and verify. After calculating, do a quick sanity check. Your answer should be at least as large as $r!$ (the minimum if you'd already chosen which $r$ items to use) and no larger than $n!$.

A common mistake is using permutations when combinations are needed, or vice versa. Always ask yourself: does swapping two selected items create a different outcome? If yes, use permutations. If no, use combinations.