6.2 Permutations and Combinations

Section 6.1 counted multi-stage choices by multiplication. That rule still applies when choices cannot repeat, but the number available at each stage now decreases.

We must also decide whether changing the order creates a new outcome. This distinction separates permutations from combinations.

Factorials count complete arrangements

Suppose $n$ distinct objects are arranged in a row.

• the first position has $n$ choices;

• after choosing one object, the second has $n-1$ choices;

• the third has $n-2$ choices;

• the process continues until the last position has $1$ choice.

By the product principle, the number of arrangements is

This product is called $n$ factorial:

For example,

We define

This convention represents the one way to arrange no objects—the empty arrangement—and makes later formulas work at boundary cases.

Permutations: order matters

A permutation is an ordered arrangement of distinct objects.

For $\{A,B,C\}$, the six permutations are

The strings $ABC$ and $BAC$ are different because their positions differ.

Arranging only $r$ of $n$ objects

An $r$-permutation of $n$ distinct objects chooses and orders $r$ objects.

The first position has $n$ choices, the second has $n-1$, and the $r$th has

choices. Therefore

Using factorials,

The denominator cancels the unused tail:

Example: podium positions

Eight runners compete for gold, silver, and bronze. One runner cannot occupy two places, and the medals are different positions. Thus

This is not $\binom83$, because choosing the same three runners in a different medal order changes the outcome.

Restrictions change the stage counts

Suppose five people $A,B,C,D,E$ sit in a row, but $A$ must occupy the first seat. The first stage is fixed, leaving

arrangements.

If $A$ and $B$ must sit together, treat them temporarily as one block. The units are

which can be arranged in $4!$ ways. Inside the block, $A,B$ can appear as $AB$ or $BA$, so

arrangements satisfy the restriction.

The block method works because every valid arrangement can be encoded uniquely as:

1. an arrangement of the block and other objects;

2. an internal ordering of the block.

Permutations with repeated types

If some objects are indistinguishable, $n!$ overcounts.

The word LEVEL has $5$ letters:

• $L$ appears $2$ times;

• $E$ appears $2$ times;

• $V$ appears $1$ time.

If the two $L$ copies were temporarily labeled $L_1,L_2$, swapping their labels would not change the visible word. Each visible arrangement is counted $2!$ times from the $L$ labels and $2!$ times from the $E$ labels.

Therefore the number of distinct arrangements is

In general, if $n$ objects contain repeated types with multiplicities

then the number of distinct arrangements is

Arrange a crew into role-sensitive stations while restrictions change in real time: fixed seats, adjacent partners, forbidden positions, and repeated badges. The vault compares raw stage products with block encodings and highlights exactly when two arrangements are distinct.

Combinations: order does not matter

A combination chooses a subset without assigning positions.

Choosing committee members $\{A,B,C\}$ produces the same committee whether the names were selected in the order

or

The number of ways to choose $r$ objects from $n$ distinct objects is written

read “$n$ choose $r$.”

Deriving the combination formula

First count ordered selections of $r$ objects:

Every unordered group of $r$ objects appears in exactly

orders. To collapse those duplicate orders, divide:

Notation across Chinese and international textbooks

The formulas do not change across regions, but the placement of the letters often does. This course uses $P(n,r)$ for ordered selections and $\binom nr$ for unordered selections. Many Chinese textbooks use $A_n^r$ and $C_n^r$, with the total number $n$ as a subscript and the selected number $r$ as a superscript. English-language sources may also write ${}_nP_r$, ${}_nC_r$, or $C(n,r)$.

Thus

Always read the definition before substituting values: $C_n^r$ and $\binom nr$ place the same two parameters in different visual positions.

Example: choosing a team

Choose $3$ people from $8$ for an unranked team:

If the selected people must then receive captain, analyst, and presenter roles, order returns:

Useful boundary values and symmetry

There is one way to choose no objects:

There is one way to choose all objects:

Choosing $r$ objects is equivalent to choosing which $n-r$ objects to leave out. The complement map is a bijection, so

For example,

The first side chooses $3$ included people; the second chooses the $7$ excluded people. Both decisions determine the same split.

A reliable order test

Ask:

> If I keep the same selected objects but reorder them, do I get a different outcome?

• If yes, use an ordered model such as a permutation.

• If no, use a combination.

Compare:

Mixed problems should be split into stages rather than forced into one formula.

Draft an unordered team from a roster, then activate roles and watch each team unfold into $r!$ ordered copies. A duplicate-collapse chamber groups selections with the same members, making the division from permutations to combinations physically visible.

Section bridge

Permutations and combinations count possibilities exactly. Some problems ask a different kind of question: without knowing the exact arrangement, what repetition is guaranteed? Section 6.3 introduces the pigeonhole principle, which proves unavoidable collisions from counts alone.