Permutations and Combinations

You have probably faced decisions like these: Which three friends should you invite to a concert when you have four tickets? In what order should you tackle your homework assignments? How many different ways could you arrange your bookshelf? These questions might seem casually different, but they share a crucial mathematical distinction: sometimes the order of your choices matters, and sometimes it does not.

If you are choosing three people for a relay race and assigning them to run first, second, and third, then order matters. The team “Alice first, Bob second, Carol third” is different from “Carol first, Alice second, Bob third” even though it is the same three people.

But if you are just choosing three people to be on a committee where everyone has equal status, then order does not matter. The committee {Alice, Bob, Carol} is the same whether you picked Alice first or last.

This distinction is the heart of permutations and combinations. Once you learn to recognize which type of problem you are facing, the calculations follow naturally.

Core Concepts

The Key Question: Does Order Matter?

Before diving into formulas, train yourself to ask one question whenever you encounter a counting problem: Does the order of selection matter?

• Order matters: You are creating an arrangement where position or sequence is important. These are called permutations.
• Order does not matter: You are making a selection where only the members matter, not their order. These are called combinations.

Here are some quick examples to build your intuition:

Situation	Does order matter?	Type
Choosing a president, VP, and treasurer from 10 candidates	Yes (different roles)	Permutation
Choosing 3 people for a committee from 10 candidates	No (all equal members)	Combination
Arranging 5 books on a shelf	Yes (different positions)	Permutation
Selecting 5 books to bring on vacation	No (just which books)	Combination
Creating a 4-digit PIN	Yes (1234 differs from 4321)	Permutation
Choosing 4 pizza toppings	No (same pizza either way)	Combination
Ranking your top 3 favorite movies	Yes (1st differs from 3rd)	Permutation
Choosing 3 movies to watch this weekend	No (just which ones)	Combination

Permutations: When Order Matters

A permutation is an arrangement of objects where the order is significant. When you select $r$ objects from a set of $n$ objects and arrange them in a specific order, you are counting permutations.

The Permutation Formula

Recall from counting principles that if you have $n$ objects and want to arrange all of them, there are $n!$ ways. But what if you only want to arrange some of them?

Suppose you have 10 people and want to select 3 of them for 1st, 2nd, and 3rd place. How many ways can this be done?

• First place: 10 choices
• Second place: 9 choices (one person already selected)
• Third place: 8 choices (two people already selected)

Total: $10 \times 9 \times 8 = 720$ ways.

This can be written more elegantly using factorials:

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

Let us verify: $P(10, 3) = \frac{10!}{(10-3)!} = \frac{10!}{7!}$

Since $10! = 10 \times 9 \times 8 \times 7!$, we get:

$$P(10, 3) = \frac{10 \times 9 \times 8 \times 7!}{7!} = 10 \times 9 \times 8 = 720$$

The formula works by canceling out the “unused” factors in the factorial.

Why this formula makes sense: You have $n$ choices for the first position, $n-1$ for the second, $n-2$ for the third, and so on until you have filled $r$ positions. This product of $r$ consecutive decreasing numbers starting from $n$ equals $\frac{n!}{(n-r)!}$.

Permutations of All Objects

When you arrange all $n$ objects (meaning $r = n$), the formula simplifies:

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

This confirms what you already knew: arranging all $n$ distinct objects yields $n!$ permutations.

Permutations with Repetition

What if you can use the same item more than once? If you are choosing $r$ items from $n$ options and repetition is allowed, then:

$$n^r$$

For example, a 4-digit PIN using digits 0-9 (repetition allowed) has $10^4 = 10,000$ possibilities.

This is different from the permutation formula because you always have $n$ choices at each step, not a decreasing number of choices.

Combinations: When Order Does Not Matter

A combination is a selection of objects where the order does not matter. When you select $r$ objects from $n$ objects and only care about which objects are chosen (not their arrangement), you are counting combinations.

The Combination Formula

Let us return to our 10-person example. If you are choosing 3 people for a committee (no assigned roles), how many ways can this be done?

From the permutation calculation, we know there are 720 ways to choose 3 people for distinct 1st, 2nd, and 3rd positions. But for a committee, the group {Alice, Bob, Carol} is the same regardless of the order we picked them. How many times did we count this same committee?

The 3 people can be arranged among themselves in $3! = 6$ ways:

• Alice, Bob, Carol
• Alice, Carol, Bob
• Bob, Alice, Carol
• Bob, Carol, Alice
• Carol, Alice, Bob
• Carol, Bob, Alice

So every committee was counted 6 times in our permutation calculation. To get the correct count, we divide:

$$\frac{720}{6} = 120 \text{ committees}$$

This leads to the combination formula:

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

The notation $\binom{n}{r}$ is read as “n choose r.”

Let us verify: $\binom{10}{3} = \frac{10!}{3! \times 7!} = \frac{10 \times 9 \times 8 \times 7!}{6 \times 7!} = \frac{720}{6} = 120$

The relationship between permutations and combinations:

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

This makes intuitive sense: combinations equal permutations divided by the number of ways to arrange the selected items (because we do not care about that arrangement).

Special Properties of Combinations

Symmetry: $\binom{n}{r} = \binom{n}{n-r}$

Choosing $r$ objects to include is the same as choosing $n-r$ objects to exclude.

For example: $\binom{10}{3} = \binom{10}{7} = 120$

Choosing 3 people for a committee is equivalent to choosing 7 people to not be on the committee.

Boundary cases:

• $\binom{n}{0} = 1$ (there is exactly one way to choose nothing)
• $\binom{n}{n} = 1$ (there is exactly one way to choose everything)
• $\binom{n}{1} = n$ (there are $n$ ways to choose one item)

Deciding Between Permutations and Combinations

Here is a systematic approach:

1. Identify what you are selecting from: How many objects in total? This is your $n$.

2. Identify how many you are selecting: How many objects are you choosing? This is your $r$.

3. Ask: Would rearranging my selection create a different outcome?

   • If YES, use permutations: $P(n, r) = \frac{n!}{(n-r)!}$
   • If NO, use combinations: $C(n, r) = \frac{n!}{r!(n-r)!}$

4. Check for repetition: Can you select the same item more than once?

   • If YES (with order mattering), use $n^r$
   • If YES (without order mattering), the formula is more complex (covered in advanced courses)

Common keywords that suggest permutations: arrange, order, rank, first/second/third, sequence, assign to positions, schedule, password, code.

Common keywords that suggest combinations: choose, select, pick, group, committee, team, hand (in cards), subset.

Pascal’s Triangle Connection

There is a beautiful pattern connecting combinations called Pascal’s Triangle. Each entry in the triangle equals a combination:

Row 0:                 1                    (n=0)
Row 1:               1   1                  (n=1)
Row 2:             1   2   1                (n=2)
Row 3:           1   3   3   1              (n=3)
Row 4:         1   4   6   4   1            (n=4)
Row 5:       1   5  10  10   5   1          (n=5)
Row 6:     1   6  15  20  15   6   1        (n=6)

The entry in row $n$, position $r$ (counting from 0) equals $\binom{n}{r}$.

For example, in row 6, position 2: $\binom{6}{2} = 15$.

The key pattern: Each entry is the sum of the two entries directly above it.

$$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$

This is called Pascal’s Identity, and it makes sense: to choose $r$ items from $n$, you either include a specific item (then choose $r-1$ from the remaining $n-1$) or exclude it (then choose all $r$ from the remaining $n-1$).

Applications to Probability

Permutations and combinations are essential tools for probability calculations. Remember:

$$P(\text{event}) = \frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}}$$

Often, both the numerator and denominator require counting using permutations or combinations.

Key insight: When selecting items randomly (where each selection is equally likely), use the same counting method for both favorable and total outcomes.

For example, if you randomly deal 5 cards from a deck, the total number of possible hands is $\binom{52}{5}$ (order does not matter for a hand). The number of favorable outcomes also uses combinations.

Notation and Terminology

Term	Meaning	Example
Permutation	Ordered arrangement	Ranking 3 winners from 10
$P(n,r)$ or $_nP_r$	Permutations of $r$ from $n$	$P(10,3) = 720$
Combination	Unordered selection	Choosing 3 people from 10
$C(n,r)$ or $\binom{n}{r}$	Combinations of $r$ from $n$	$\binom{10}{3} = 120$
“n choose r”	Spoken form of $\binom{n}{r}$	“10 choose 3” equals 120
$n!$	n factorial	$5! = 120$
With replacement	Items can be selected more than once	Drawing a card, replacing it, drawing again
Without replacement	Items can only be selected once	Dealing cards from a deck

Examples

Key Properties and Rules

Permutation Formulas

Permutations of $r$ items from $n$ (without repetition): $$P(n, r) = \frac{n!}{(n-r)!} = n \times (n-1) \times (n-2) \times \cdots \times (n-r+1)$$

Permutations of all $n$ items: $$P(n, n) = n!$$

Permutations with repetition allowed: $$n^r$$

Combination Formulas

Combinations of $r$ items from $n$: $$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Relationship to permutations: $$\binom{n}{r} = \frac{P(n, r)}{r!}$$

Key Properties

Symmetry: $$\binom{n}{r} = \binom{n}{n-r}$$

Pascal’s Identity: $$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$

Sum of a row in Pascal’s Triangle: $$\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n$$

Boundary values: $$\binom{n}{0} = \binom{n}{n} = 1$$ $$\binom{n}{1} = \binom{n}{n-1} = n$$

Decision Guide

Question	If YES	If NO
Does order/arrangement matter?	Permutation	Combination
Can items be repeated?	Use $n^r$ (if order matters)	Use standard formulas
Are there assigned positions/roles?	Permutation	Combination
Does rearranging give a different outcome?	Permutation	Combination

Real-World Applications

Lottery and Gambling Odds

Lotteries are pure combination problems. When Powerball asks you to choose 5 numbers from 69 (plus a Powerball from 26), the odds against winning the jackpot are calculated using combinations:

$$\binom{69}{5} \times 26 = 292,201,338$$

That is nearly 1 in 300 million odds. Understanding these calculations helps you make informed decisions about gambling.

Poker and Card Games

Every poker probability involves combinations. The total number of 5-card hands ($\binom{52}{5} = 2,598,960$) is the denominator, and the number of hands matching specific patterns (flush, straight, full house, etc.) forms the numerator.

Professional players understand these odds intuitively. A “pocket pair” in Texas Hold’em happens about once every 17 hands because $\binom{4}{2} \times 13 = 78$ pocket pairs exist among $\binom{52}{2} = 1,326$ possible starting hands.

Scheduling and Seating

Permutations arise in scheduling problems. If a conference has 8 speakers and 8 time slots, there are $8! = 40,320$ possible schedules. Adding constraints (some speakers must go before others, some cannot speak at certain times) creates restricted permutation problems.

Seating arrangements at round tables, wedding receptions, or classroom seating all involve permutations, sometimes with interesting twists like circular arrangements where rotations are considered equivalent.

Committee and Team Selection

Organizations constantly face combination problems. How many ways can a company form a project team of 5 from 20 employees? That is $\binom{20}{5} = 15,504$ possible teams. If the team needs a leader and deputy (adding structure), permutations enter the picture.

Sports drafts, jury selection, and academic admissions all involve similar counting problems at much larger scales.

Computer Science and Security

Password security directly relates to permutations with repetition. A password of length $k$ using an alphabet of $n$ characters has $n^k$ possibilities. This is why security experts recommend longer passwords with more character types.

Combination locks (ironically named since they typically use permutations) with 40 numbers and 3-number codes have $40 \times 40 \times 40 = 64,000$ combinations if numbers can repeat, or $40 \times 39 \times 38 = 59,280$ if they cannot.

Genetics and Biology

In genetics, combinations help calculate the number of ways genes can combine during reproduction. If a trait is controlled by selecting $r$ alleles from $n$ possible alleles, combinations give the number of possible genotypes.

Drug trial design uses combinations to determine how many ways patients can be assigned to treatment and control groups.

Self-Test Problems

Summary

• Permutations count arrangements where order matters. Use when positions, rankings, or sequences are important. $$P(n, r) = \frac{n!}{(n-r)!}$$

• Combinations count selections where order does not matter. Use when only the members of a group matter, not their arrangement. $$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

• The key question: Does rearranging the selection give a different outcome? If yes, use permutations. If no, use combinations.

• The relationship: $\binom{n}{r} = \frac{P(n,r)}{r!}$ because combinations “divide out” the orderings that permutations count.

• Permutations with repetition: When the same item can be chosen multiple times and order matters, use $n^r$.

• Pascal’s Triangle displays all combination values, with each entry being the sum of the two entries above it.

• Symmetry property: $\binom{n}{r} = \binom{n}{n-r}$. Choosing $r$ items to include is equivalent to choosing $n-r$ items to exclude.

• Applications to probability: Use combinations or permutations to count both favorable outcomes and total outcomes. Use the same method for both to ensure consistency.

• Real-world applications include lottery odds, poker hands, scheduling, committee selection, password security, and genetics.

• Decision tip: Look for keywords like “arrange,” “rank,” or “order” (permutation) versus “choose,” “select,” or “group” (combination).