6.3 Permutations & Combinations

Two questions decide almost everything: does order matter? and can things repeat? This section covers the case with no repetition. (Repetition is 6.5.)

Permutations

Permutation

A permutation of a set of distinct objects is an ordered arrangement of them. An $r$ -permutation is an ordered arrangement of $r$ of them.
$P (n, r) = n (n - 1) (n - 2) \dots (n - r + 1) = \frac{n !}{( n - r )!}$
In particular $P (n, n) = n!$ and $P (n, 0) = 1$ .

From class

4 of 6 students standing in a line: $P (6, 4) = 6 \cdot 5 \cdot 4 \cdot 3 = 360$ .
1st, 2nd, 3rd prize among 50 contestants: $P (50, 3) = 50 \cdot 49 \cdot 48 = 117, 600$ .
Permutations of ABCDEFG containing EFG as a substring: glue EFG into one block, giving 5 units, so $5! = 120$ .

Combinations

Combination

An $r$ -combination is an unordered selection (a subset) of $r$ elements.
$C (n, r) = (r n) = \frac{n !}{r ! ( n - r )!}$

Where the formula comes from (from class)

Build an $r$ -permutation in two steps: choose the $r$ objects ( $(r n)$ ways), then arrange them ( $r!$ ways). So
$P (n, r) = (r n) \cdot r! ⟹ (r n) = \frac{P ( n , r )}{r !} .$
Symmetry: $(r n) = (n - r n)$ . Choosing who's in is the same as choosing who's out. That's why 5-card hands and 47-card hands from 52 cards are equal in number.

Order matters?

	Order matters	Order doesn't matter
Words that signal it	arrange, line up, ranking, 1st/2nd/3rd, officers with titles, strings	committee, subset, hand of cards, team, group, choose
Count	$P (n, r)$	$C (n, r)$

Standard patterns

Bit strings with

k

ones

A length- $n$ bit string with exactly $k$ ones is determined by which positions hold the 1s: $(k n)$ .

"At most $k$ ": $\sum_{i = 0}^{k} (i n)$
"At least $k$ ": $2^{n} - \sum_{i = 0}^{k - 1} (i n)$ , using the complement when that is shorter.

Same for coin flips (heads = 1).

Substrings: glue blocks together

Required substring(s): glue each into a block and permute the blocks plus the leftover letters.
Two required substrings that overlap (share letters, like ABC and CDE): merge them into one block (ABCDE).
Two required substrings that conflict (like CBA and BED, where B would need two different followers): the answer is $0$ .

"No two X adjacent": the gap method

Arrange the others first, then choose gaps for the X's. With $m$ others there are $m + 1$ gaps (including both ends), and you place the X's into distinct gaps.

8 men and 5 women, no two women adjacent: $8! \cdot P (9, 5)$ .

Committees with constraints

Exactly $a$ from group 1 and $b$ from group 2: $(a n _{1}) (b n _{2})$ (product rule).
At least one woman: $(r all) - (r men)$ .
At least one woman and at least one man: $(r all) - (r men) - (r women)$ .

Never count "at least one" as "choose one, then choose the rest"

$(1 7) (4 15)$ for "at least one woman" counts committees with 2 women twice, once for each woman picked first. Use the complement.

Circular

r

-permutations

Seating $r$ of $n$ people around a table, rotations equal: $\frac{P ( n , r )}{r}$ . This is the division rule from 6.1.

Combinatorial proofs

A combinatorial proof shows an identity by explaining that both sides count the same set (double counting), or by building a bijection.

Example: $(r n) = (n - r n)$ . Both sides count the $r$ -subsets of an $n$ -set: the left chooses the members, the right chooses the non-members.

Arithmetic without a calculator

Binomial values worth memorizing

$(0 n) = 1$ , $(1 n) = n$ , $(2 n) = \frac{n ( n - 1 )}{2}$
Row 5: 1, 5, 10, 10, 5, 1
Row 6: 1, 6, 15, 20, 15, 6, 1
Row 8: 1, 8, 28, 56, 70, 56, 28, 8, 1
Row 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1
$\sum_{k} (k n) = 2^{n}$ (e.g. $2^{10} = 1024$ )

To compute $(r n)$ by hand, write $\frac{n ( n - 1 ) \dots ( n - r + 1 )}{r !}$ and cancel before multiplying. Example: $(4 12) = \frac{12 \cdot 11 \cdot 10 \cdot 9}{4 \cdot 3 \cdot 2 \cdot 1} = 11 \cdot 5 \cdot 9 = 495$ .

About your class notes

Your notes write $C (n, r) =_{n} C_{r} = (k n)$ . The bottom should be $r$ , i.e. $(r n)$ . Everything else matches.

Exam checklist

Decide permutation vs. combination from the wording.
Compute $P (n, r)$ and $(r n)$ by hand (cancel first!).
Bit strings or coin flips with exactly / at most / at least $k$ .
Substring problems (glue blocks; overlaps merge; conflicts give 0).
No-two-adjacent problems (gap method).
Committees with "exactly" and "at least" constraints.