Permutations & Combinations
The mathematics of counting without listing — when order matters, and when it does not
- The multiplication and addition principles — the engine behind all counting.
- Permutations \({}^{n}P_r\): arranging, with and without repetition, and with identical objects.
- Circular arrangements, and the necklace correction.
- Combinations \({}^{n}C_r\), their key properties, and Pascal's rule.
- To divide and distribute objects into groups and boxes.
- Stars and bars for selections with repetition and integer-solution counts.
The Art of Counting
How many four-digit PINs are there? How many ways can a team be chosen? Listing them all is hopeless — but we rarely need to. Combinatorics counts the size of a collection without writing it out, and everything rests on two simple principles.
Multiplication: if one stage can happen in \(m\) ways and a following stage in \(n\) ways, the whole job has \(m\times n\) outcomes. Addition: if a task is done by one method in \(m\) ways or a mutually exclusive method in \(n\) ways, there are \(m+n\) ways.
Factorials
Counting arrangements quickly produces products like \(5\times4\times3\times2\times1\), so we give them a name:
Permutations: Arranging Things
A permutation is an ordered arrangement. To arrange \(r\) objects chosen from \(n\) distinct ones, fill \(r\) positions in turn: \(n\) choices for the first, \(n-1\) for the second, and so on.
Arranging all \(n\) objects gives \({}^{n}P_n=n!\). The phrase "order matters," "arrange," "rank," or "form a word/number" signals a permutation.
Repetition & Identical Objects
Two twists change the count. (a) Repetition allowed: if each position may reuse any object, every one of the \(r\) slots has all \(n\) choices — this is how PINs and number plates are counted. (b) Identical objects: if some objects are indistinguishable, swapping them produces no new arrangement, so we divide them out.
| Situation | Count |
|---|---|
| \(r\) from \(n\), no repetition | \({}^{n}P_r=\dfrac{n!}{(n-r)!}\) |
| \(r\) places, repetition allowed | \(n^{\,r}\) |
| All \(n\), with \(p,q,\dots\) alike | \(\dfrac{n!}{p!\,q!\cdots}\) |
Circular Permutations
Around a round table there is no "first" seat — rotating everyone one place to the left changes nothing. So we fix one person as a reference and arrange the rest, which removes the \(n\) identical rotations.
If clockwise and anticlockwise arrangements are considered the same (a necklace or garland that can be flipped), halve it to \(\dfrac{(n-1)!}{2}\).
Combinations: Selecting Things
A combination is a selection where order is irrelevant — a committee, a hand of cards, a subset. Since each group of \(r\) objects can be arranged in \(r!\) orders, we take the permutation count and divide that excess away.
The bridge between the two ideas: \({}^{n}P_r={}^{n}C_r\times r!\) — select, then arrange. "Choose," "select," "committee," or "how many ways to pick" all flag a combination.
Before counting anything, ask: does the order of the chosen objects matter? If yes → permutation. If no → combination. Getting this wrong is the single most common error in the whole chapter.
Properties of nCr
| Identity | Meaning |
|---|---|
| \({}^{n}C_r={}^{n}C_{n-r}\) | choosing \(r\) to keep = choosing \(n-r\) to drop |
| \({}^{n}C_r+{}^{n}C_{r-1}={}^{n+1}C_r\) | Pascal's rule — builds Pascal's triangle |
| \({}^{n}C_0+{}^{n}C_1+\dots+{}^{n}C_n=2^{n}\) | total number of subsets of an \(n\)-set |
| \({}^{n}C_x={}^{n}C_y\Rightarrow x=y\) or \(x+y=n\) | when two combinations are equal |
| \(r\cdot{}^{n}C_r=n\cdot{}^{n-1}C_{r-1}\) | absorbs a factor — handy in series |
Distributing & Grouping Objects
Many problems ask us to split objects into groups or scatter them into boxes. The counts depend on whether the objects are distinct, and whether the groups are labelled.
| Task | Count |
|---|---|
| \(n\) distinct into labelled groups \(p,q,r\) \((p+q+r=n)\) | \(\dfrac{n!}{p!\,q!\,r!}\) |
| \(n\) distinct into \(k\) equal, unlabelled groups | \(\dfrac{n!}{(p!)^{k}\,k!}\) |
| \(n\) distinct objects into \(r\) distinct boxes | \(r^{\,n}\) |
If the groups have identities (Group A, Group B), do not divide by the number of groups. If they are interchangeable (just "three piles of equal size"), you must divide by \(k!\) to remove the relabelling overcount.
Combinations with Repetition (Stars & Bars)
How many ways can you pick 7 identical candies and split them among 3 children (some possibly getting none)? Picture the 7 candies as stars and use 2 bars to partition them into 3 groups:
Equivalently, choosing \(r\) objects from \(n\) types with repetition can be done in \({}^{\,n+r-1}C_{\,r}\) ways. You are simply deciding where to place the dividing bars among the stars.
Strategies & Standard Results
A few reliable tactics turn intimidating problems into routine ones.
Count the opposite and subtract from the total. "At least one" is often easiest as (total) − (none).
For "no two together," arrange the others first, then drop the restricted items into the gaps between them.
For "must be together," tie the group into one block, arrange blocks, then arrange within the block.
Putting It to Work
Problem. How many 3-digit numbers can be formed from the digits \(1,2,3,4,5\) (a) with no digit repeated, (b) with repetition allowed?
Solution. (a) Order matters and no repetition: \({}^{5}P_3=5\times4\times3=60\). (b) Each of the 3 places has all 5 choices: \(5^{3}=125\).
Problem. How many distinct arrangements are there of the letters of MISSISSIPPI?
Solution. 11 letters with M(1), I(4), S(4), P(2). Divide out the identical letters:
Problem. From 7 men and 5 women, how many committees of 5 contain at least 3 women?
Solution. "At least 3 women" splits into 3, 4, or 5 women, filling the rest with men:
Problem. In how many ways can 4 boys and 3 girls sit in a row so that no two girls are adjacent?
Solution. Seat the 4 boys first: \(4!=24\) ways. This creates 5 gaps (including the ends). Place the 3 girls into 3 different gaps: \({}^{5}P_3=60\). By the multiplication principle, \(24\times60=1440\).
Problem. In how many ways can 10 identical chocolates be distributed among 4 children?
Solution. Non-negative solutions of \(x_1+x_2+x_3+x_4=10\):
Problem. How many positive divisors does \(360\) have?
Solution. Factor: \(360=2^{3}\cdot3^{2}\cdot5^{1}\). The number of divisors is \((3+1)(2+1)(1+1)=4\cdot3\cdot2=24\).
Chapter Summary
AND → multiply, OR → add. Every formula in the chapter is built from these two.
\({}^{n}P_r=\tfrac{n!}{(n-r)!}\); \(n^r\) with repetition; \(\tfrac{n!}{p!q!\cdots}\) for like objects.
\((n-1)!\) around a table; \(\tfrac{(n-1)!}{2}\) for a flippable necklace.
\({}^{n}C_r=\tfrac{n!}{r!(n-r)!}\); symmetry, Pascal's rule, and \(\sum{}^{n}C_r=2^n\).
Labelled vs unlabelled groups; \(r^n\) for distinct objects into distinct boxes.
\({}^{n+r-1}C_{r-1}\) for non-negative integer solutions / selection with repetition.
Problems
For each, first decide whether order matters. Difficulty rises down the list.
- How many 4-digit numbers, with no repeated digit, can be formed from \(0,1,2,3,4,5\) (the number may not start with 0)?
- How many distinct words can be formed from the letters of ARRANGE? In how many of them do the two R's come together?
- In how many ways can 8 people be seated around a circular table? What if two particular people must sit together?
- Find \(n\) if \({}^{n}C_8={}^{n}C_{12}\), and evaluate \({}^{n}C_{2}\).
- From a deck of 52 cards, how many 5-card hands contain exactly 2 aces?
- How many diagonals does a convex polygon with \(n\) sides have?
- In how many ways can a group of 12 students be split into three labelled teams of 4, 4, and 4? And into three unlabelled teams of equal size?
- How many non-negative integer solutions are there to \(x_1+x_2+x_3=15\)? How many positive integer solutions?
- A student must answer 7 of 10 questions, but at least 3 from the first 5. In how many ways can the choice be made?
- How many four-letter words can be formed using the letters of EXAMINATION?
- Find the number of ways to place 6 identical rings on 4 fingers of one hand (a finger may hold several, order on a finger does not matter).
- How many integers between 1 and 1000 are divisible by neither 2, 3, nor 5? (Use complementary counting / inclusion–exclusion.)