Applications — Arrangement and Selection Problems

Telling a permutation problem from a combination problem

Every word problem in this chapter reduces to one question: if the same objects were chosen in a different order, would the outcome actually be different?

• Yes → use $^{n}P_{r}$. Examples: arranging books on a shelf, forming a number from digits, appointing a Chairperson and a Secretary (two DIFFERENT roles), deciding 1st/2nd/3rd prize.
• No → use $^{n}C_{r}$. Examples: forming a committee, choosing a team, selecting a set of books to buy (without arranging them).

Worked reasoning for common problem types

• Arranging all $n$ distinct objects in a row: $n!$ ways (this is simply $^{n}P_{n}$).
• Arranging $r$ out of $n$ distinct objects: $^{n}P_{r}$ ways.
• Selecting $r$ out of $n$ distinct objects (no arranging): $^{n}C_{r}$ ways.
• Selecting AND then arranging $r$ out of $n$ objects: this is exactly $^{n}P_{r}$ again — never computed separately as $^{n}C_{r} \times r!$ from scratch, because $^{n}C_{r} \times r! = {}^{n}P_{r}$ always (the very identity used to derive the $^{n}C_{r}$ formula above).
• Number of diagonals of a polygon with $n$ vertices: every pair of vertices gives a line segment ($^{n}C_{2}$ of them in all), and exactly $n$ of those segments are SIDES of the polygon, not diagonals — so the diagonal count is $^{n}C_{2} - n$. …