Discrete Math › Section D · Counting › Topic D.4
Combinations and permutations
Choosing a team and choosing a team with ranked positions are different questions with different answers. Permutations count ordered selections, combinations count unordered ones, and one division links the two.
Does order matter?
Pick 3 of a club's 11 members. If the three become chair, vice-chair and treasurer, then swapping two of them gives a different outcome. If the three simply form a committee, swapping changes nothing. The first question counts sequences, called permutations; the second counts sets, called combinations. Both build on the product principle from "The sum and product principles", and both connect to the entries \(\binom{n}{k}\) of Pascal's triangle. This topic finally gives those entries a closed formula, so you no longer need to build the triangle row by row. (The statistics course covers the same tools in "Counting, permutations, and combinations".)
Arranging everything: n factorial
In how many orders can \(n\) different objects be arranged? The first position has \(n\) options, the second \(n - 1\), and so on down to 1, so by the product principle the count is
Seven different books fit on a shelf in \(7! = 5040\) orders. By convention \(0! = 1\): there is exactly one way to arrange nothing, and the convention keeps later formulas valid at the edges. Each arrangement of a set \(A\) with \(n\) elements is the same thing as a bijection from \(A\) to itself, so there are \(n!\) such bijections.
Ordered selections: k-permutations
A \(k\)-permutation of \(n\) elements is a sequence of \(k\) different elements chosen from the \(n\). The product principle gives \(n\) options, then \(n - 1\), down to \(n - k + 1\), so
The club's three officers can be chosen in \(P(11, 3) = 11 \cdot 10 \cdot 9 = 990\) ways. In the language of functions, a \(k\)-permutation is an injective (one-to-one) function from a \(k\)-element set into an \(n\)-element set: each position gets a different element. So there are \(P(n, k)\) injections, and none at all when \(k > n\).
Unordered selections: the formula for n choose k
Every \(k\)-permutation can be produced in two stages: first choose which \(k\) elements to use, a \(k\)-element subset, in \(\binom{n}{k}\) ways; then arrange them, in \(k!\) ways. So \(P(n, k) = \binom{n}{k} \cdot k!\), and dividing gives
This agrees with Pascal's triangle, because \(\binom{n}{k}\) still counts \(k\)-element subsets. For instance \(\binom{7}{3} = \frac{5040}{6 \cdot 24} = 35\), the entry in row 7, position 3. The club can form a three-person committee in \(\frac{990}{6} = 165\) ways: each committee appeared \(3! = 6\) times among the 990 officer lists.
Worked example: a committee with a chair
From 11 members, how many ways are there to form a 4-person committee with one member named chair? 1. Choose the committee, then its chair: \(\binom{11}{4} \cdot 4 = 330 \cdot 4 = 1320\). 2. Count a second way: choose the chair first, in 11 ways, then the other 3 members from the remaining 10: \(11 \cdot \binom{10}{3} = 11 \cdot 120 = 1320\). 3. The two methods agree, which is a strong check. 4. Compare with a committee and no chair, \(330\): naming a chair multiplies the count by 4, because each committee can be led by any of its 4 members. Counting the same set in two ways is the idea behind "Combinatorial proofs".
The quotient principle
The step from \(P(n, k)\) to \(\binom{n}{k}\) is an example of a general rule. If a set of \(N\) things splits into groups that each contain exactly \(d\) things, there are \(N / d\) groups. Use it whenever an easy count lists every outcome the same number of times. Seat 6 people at a round table, where only the order around the table matters, not which chair anyone takes, so moving everyone one chair to the left gives the same seating. There are \(6! = 720\) ways to fill the chairs, but each seating appears 6 times, once for each rotation. So there are \(720 / 6 = 120\) different seatings, which is \((6 - 1)!\). The division is valid only because every seating repeats exactly 6 times.
Arrangements with repeated letters
How many different strings can be made by rearranging SUCCESS? If its 7 letters were all different there would be \(7!\). But swapping the three S's among themselves, in \(3!\) ways, or the two C's, in \(2!\) ways, leaves the word unchanged, so each string appears \(3! \cdot 2! = 12\) times. By the quotient principle there are
strings. A second route: choose positions for the S's, \(\binom{7}{3} = 35\), then for the C's among the 4 left, \(\binom{4}{2} = 6\), then for U, 2 ways, with E taking the last spot: \(35 \cdot 6 \cdot 2 = 420\).
Worked example: hands of cards
A standard deck has 52 cards, 4 of them aces. How many 5-card hands contain exactly two aces? 1. A hand is a set of cards, so order does not matter: use combinations. 2. Choose the 2 aces from 4: \(\binom{4}{2} = 6\). 3. Choose the other 3 cards from the 48 non-aces: \(\binom{48}{3} = \frac{48 \cdot 47 \cdot 46}{6} = 17{,}296\). 4. By the product principle, \(6 \cdot 17{,}296 = 103{,}776\) hands. 5. For scale, the total number of hands is \(\binom{52}{5} = 2{,}598{,}960\), so about 4% of hands have exactly two aces. Turning such counts into probabilities is the job of a later topic, "Counting and probability".
Choosing the right tool
Ask two questions about a selection of \(k\) items from \(n\) types. Does order matter? Can an item be used more than once? Ordered with repetition, like PINs, gives \(n^k\). Ordered without repetition, like officers, gives \(P(n, k)\). Unordered without repetition, like committees, gives \(\binom{n}{k}\). The fourth case, unordered with repetition, like a bag of fruit with several of the same kind, needs a new idea and is the subject of "Counting multisets (stars and bars)". When a problem has extra conditions, combine these counts with the sum principle, complements and inclusion-exclusion.
Common mistakes to avoid
First, using \(P(n, k)\) for a committee or a hand of cards, which counts each set \(k!\) times. Second, using \(\binom{n}{k}\) when positions or ranks are named, which undercounts. Third, forgetting \(0! = 1\), which breaks \(\binom{n}{0}\) and \(\binom{n}{n}\). Fourth, dividing by a repetition factor that is not the same for every outcome: the quotient principle needs every outcome counted exactly \(d\) times. Fifth, for repeated letters, dividing by the number of repeated letters instead of by the factorial of each repeat count.
Key takeaways
There are \(n!\) arrangements of \(n\) different objects, with \(0! = 1\). Ordered selections of \(k\) from \(n\) number \(P(n, k) = \frac{n!}{(n-k)!}\), which also counts injective functions. Unordered selections number \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\), because each set can be ordered in \(k!\) ways. The quotient principle divides out uniform overcounting, as in round tables and words with repeated letters. Always decide first whether order matters and whether repetition is allowed.
Flashcards
Flashcard
n(n − 1)···2 · 1, the arrangements of n different objects
Test your understanding
Question 1 of 5
In how many ways can a president, a secretary and a treasurer be chosen from 12 members, with no one holding two offices?
Question 2 of 5
A student must choose 3 electives from a list of 9 different courses. How many choices are there?
Question 3 of 5
How many different strings can be made by rearranging the letters of LEVEL?
Question 4 of 5
In how many different ways can 5 people sit at a round table, if only the order around the table matters?
Question 5 of 5
A team of 5 is chosen from 6 women and 4 men. How many teams contain exactly 3 women?
