math.wiki
Probability › Counting › Combinations
Open on the map
Algebra 2 · S.CP.B.9

Combinations

A pizza can have any 4 of 9 toppings. Picking the toppings one after another gives thousands of orders, so why are there only 126 different pizzas?

You need
Arrangements and factorialsAlgebra 2
Unlocks
Combinations with repetition: stars and barsDiscrete Mathematics and ProofInclusion-exclusion for three or more sets, and derangementsDiscrete Mathematics and ProofPascal's triangleAlgebra 2
Where you are 10 in Counting
Probability4
Counting10
Arrangements and factorials
Combinations
Combinations with repetition: stars and barsInclusion-exclusion for three or more sets, and derangementsProbability with counting formulas▾ Show all 10 (5 more)

Why this exists

Many counting questions ask for a choice, not a line-up. A pizza gets 4 toppings, a committee gets 5 members, a hand of cards gets 5 cards. Nobody cares which topping went on first: a pizza with mushrooms, olives, peppers and onions is the same pizza however the cook picked them.

The fundamental counting principle counts choices made one after another, so it counts ordered lists. For a choice where order does not matter that overcounts, and by a known amount: each choice of r objects shows up once for every one of its arrangements, which is r! times. Dividing that out gives the number of combinations, one of the most used numbers in mathematics. This lesson is about that number: its symbol, its formula and why the formula divides, the fact that choosing what to take is the same as choosing what to leave, choosing from several groups at once, and how to tell whether a question wants order to matter.

Definition

A combination of r objects from a set of n different objects is a choice of r of them in which order does not matter. In the language of sets, it is a subset with exactly r elements: \{A, B\} and \{B, A\} are the same subset, because a set is decided only by what is in it.

The number of combinations of r objects from n different objects is written

\binom{n}{r}

and read “n choose r”. Here n and r are whole numbers with 0 \le r \le n. The same number is also written C(n, r) or {}_{n}C_{r}; all three mean the same count.

Compare this with putting r of the n objects in order, where the first pick, second pick and so on are told apart. That number is the count of permutations, written P(n, r). The fundamental counting principle gives it at once: n choices for the first place, n - 1 for the second, down to n - r + 1 for the r-th, so

P(n, r) = n(n - 1)\cdots(n - r + 1) = \frac{n!}{(n - r)!}

Intuition

Take the letters A, B, C and D and choose 2 of them. In order, there are 4 \times 3 = 12 pairs: 4 letters can go first and then 3 are left. But AB and BA pick the same two letters. Sort the 12 ordered pairs by which two letters they use, and every set of two letters collects exactly 2! = 2 of them.

{A, B} AB BA {A, C} AC CA {A, D} AD DA {B, C} BC CB {B, D} BD DB {C, D} CD DC
Figure 1The 12 ordered pairs of different letters from A, B, C, D fall into groups of 2! = 2, one group for each set, so there are \displaystyle \frac{12}{2} = 6 sets of two letters.

So \displaystyle \binom{4}{2} = \frac{12}{2} = 6. The same thing happens for any n and r. List the ordered choices of r objects, then sort them by which objects they use. Each group holds every order of one fixed set of r objects, and r different objects have r! orders. All the groups are the same size, so the number of groups is the number of ordered choices divided by r!.

The second picture to keep is a light switch on every object. A choice of r objects from n turns r switches on and leaves n - r off. Saying which are on says which are off, which is why choosing 3 from 20 and choosing 17 from 20 give the same count.

Results

The formula. For whole numbers 0 \le r \le n,

\binom{n}{r} = \frac{n!}{r!\,(n - r)!}

The working form. Canceling (n - r)! leaves r factors on top:

\binom{n}{r} = \frac{n(n - 1)\cdots(n - r + 1)}{r!}

Ordered and unordered. The two counts differ by exactly the orders of the chosen objects:

P(n, r) = r! \binom{n}{r}

Symmetry. Choosing r objects to take is the same as choosing n - r to leave:

\binom{n}{r} = \binom{n}{n - r}

The edges. \binom{n}{0} = \binom{n}{n} = 1 and \binom{n}{1} = \binom{n}{n - 1} = n.

Several groups. To choose r_1 objects from a group of n_1, and r_2 from a separate group of n_2, and so on, multiply:

\binom{n_1}{r_1}\binom{n_2}{r_2}\cdots
Why it is true

Why the formula divides by r!. Count the ordered choices of r objects from n in two ways.

First way: the fundamental counting principle gives P(n, r) = \dfrac{n!}{(n - r)!}.

Second way, in two stages. Stage one: choose which r objects are used, in \binom{n}{r} ways. Stage two: put those r objects in order, in r! ways, the same number whichever set was chosen. Every ordered choice comes from exactly one pair of stages, because an ordered list tells you both which objects it uses and in what order. So the number of ordered choices is \binom{n}{r} \times r!.

The two counts are of the same thing, so they are equal:

r! \binom{n}{r} = \frac{n!}{(n - r)!}

and dividing both sides by r!, which is never zero, gives \binom{n}{r} = \dfrac{n!}{r!\,(n - r)!}.

Why the working form is the same number. Write n! = n(n - 1)\cdots(n - r + 1) \times (n - r)!, the first r factors and then the rest. The (n - r)! cancels with the one underneath.

Symmetry. Matching each r-element subset with the n - r objects it leaves out pairs the r-element subsets one to one with the (n - r)-element subsets: different subsets leave out different objects, and every set of n - r objects is the leftover of exactly one r-element subset, namely everything else. A one-to-one matching means the counts are equal. The formula shows it too: replacing r by n - r turns r!\,(n - r)! into (n - r)!\,r!, the same product in the other order, by the commutative property of multiplication.

The edges. There is exactly one way to choose nothing (the empty set) and exactly one way to choose everything, so \binom{n}{0} = \binom{n}{n} = 1; the formula agrees because 0! = 1. Choosing 1 object means naming it, in n ways, and symmetry gives \binom{n}{n - 1} = n.

Several groups. The choice from the first group does not change how many ways there are to choose from the second, because the groups share no objects. So the fundamental counting principle multiplies the counts.

Worked examples

Example 1

Toppings on a pizza

Hartley orders a pizza with 4 different toppings from a menu of 9. How many different pizzas can he order? Find the answer by dividing out the orders, and then by the formula.

Solution

A pizza is decided by which toppings are on it, not by the order they were named, so this is a combination.

By dividing out the orders: naming 4 toppings one after another can go 9 \times 8 \times 7 \times 6 = 3{,}024 ways. Each pizza is named in 4! = 24 of those ways, one for each order of its 4 toppings. So

\frac{3{,}024}{24} = 126

By the formula, canceling 5! first:

\begin{aligned} \binom{9}{4} &= \frac{9!}{4!\,5!} \\ &= \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126 \end{aligned}

There are 126 different pizzas. Check by symmetry: \binom{9}{5}, the number of ways to choose the 5 toppings left off, is \dfrac{9!}{5!\,4!}, the same fraction, so it is also 126.

Example 2

Games in a league

Fourteen teams play in a league.

(a) If every team plays every other team once, how many games are there?

(b) If instead every pair of teams plays twice, once at each team’s home ground, how many games are there?

Solution

(a) A game is decided by which two teams are in it: the game between the Hawks and the Owls is the same game as the one between the Owls and the Hawks. So the games match the 2-element subsets of the 14 teams:

\binom{14}{2} = \frac{14 \times 13}{2 \times 1} = \frac{182}{2} = 91

(b) Now a game is decided by an ordered pair: the home team, then the visitors. The Hawks at home to the Owls is a different game from the Owls at home to the Hawks. This is P(14, 2):

14 \times 13 = 182

The second count is exactly 2! = 2 times the first, because each pair of teams now meets in both of its orders.

Example 3

Taking or leaving

Find \binom{20}{17} without working out any factorial in full, and explain what the answer counts when a class of 20 chooses 17 of its members to go on a trip.

Solution

Taking 17 is the same as leaving 3 behind, so by symmetry

\begin{aligned} \binom{20}{17} = \binom{20}{3} &= \frac{20 \times 19 \times 18}{3 \times 2 \times 1} \\ &= \frac{6{,}840}{6} = 1{,}140 \end{aligned}

Working straight from the formula gives the same result after more canceling: \dfrac{20!}{17!\,3!} is exactly the same fraction as \dfrac{20!}{3!\,17!}. The working form with r = 17 would have 17 factors on top and 17! underneath; symmetry trades it for 3 factors.

In the trip, every list of the 17 who go is decided by the 3 who stay, and the other way round. There are 1{,}140 ways to choose the travelers.

Example 4

Order or no order

A florist has thirteen different flowers, one stem of each.

(a) Three vases stand in a row on a windowsill, left, middle and right. In how many ways can three of the flowers be put in them, one flower in each vase?

(b) In how many ways can three of the flowers be tied together into one bouquet?

Solution

The test for whether order matters: swap two of the chosen objects and ask whether the outcome changes.

(a) Swapping the flowers in the left and middle vases gives a different windowsill, so order matters. Any of the 13 can go in the left vase, then 12 are left for the middle and 11 for the right:

P(13, 3) = 13 \times 12 \times 11 = 1{,}716

(b) Swapping two flowers in a bouquet changes nothing about the bouquet, so order does not matter:

\begin{aligned} \binom{13}{3} &= \frac{13 \times 12 \times 11}{3 \times 2 \times 1} \\ &= \frac{1{,}716}{6} = 286 \end{aligned}

Check with the link between the two counts: 3! \times 286 = 6 \times 286 = 1{,}716. The three flowers of each bouquet can stand in the three vases in 3! = 6 ways.

Example 5

Choosing from two groups

A choir has 6 tenors and 8 altos, all different people. A group of 5 singers is chosen to perform at a fair.

(a) How many groups have exactly 2 tenors?

(b) How many groups have at least 1 tenor?

Solution

(a) Exactly 2 tenors in a group of 5 means exactly 3 altos. Choose the tenors in \binom{6}{2} ways and, whichever tenors were chosen, the altos in \binom{8}{3} ways. The groups share nobody, so the counts multiply:

\binom{6}{2}\binom{8}{3} = 15 \times 56 = 840

(b) “At least 1” covers 1, 2, 3, 4 or 5 tenors, five separate cases. It is shorter to count everything and take away the groups with no tenor. Any 5 of the 14 singers: \binom{14}{5} = 2{,}002. No tenor means all 5 are altos: \binom{8}{5} = \binom{8}{3} = 56. So

2{,}002 - 56 = 1{,}946

groups have at least one tenor. Each of the 2{,}002 groups either has no tenor or has at least one, never both, so the subtraction counts each group once.

Example 6

Choosing places, not things

The answer key for a 10-question true or false quiz has exactly 4 answers “true”. How many such answer keys are there?

Solution

An answer key is fixed once you know which questions are “true”: the other 6 are “false”. So a key is a choice of 4 question numbers out of 10, and the order in which they are named does not matter:

\begin{aligned} \binom{10}{4} &= \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} \\ &= \frac{5{,}040}{24} = 210 \end{aligned}

The same number appears another way. A key is a row of 10 letters, four T’s and six F’s. If all 10 letters were different there would be 10! rows, but swapping T’s among themselves, in 4! ways, or F’s among themselves, in 6! ways, gives the same row. So the number of rows is \dfrac{10!}{4!\,6!}, which is the formula for \binom{10}{4}. Combinations count rows of two kinds of identical objects, by choosing the places for one kind.

Boundaries

The objects must be different. \binom{n}{r} counts subsets of a set of n distinct objects. Choosing 2 fruits from a bowl of 5 identical apples can be done in only 1 way, not \binom{5}{2} = 10.

Each object is chosen at most once. A combination has no repeats. Choosing 3 scoops from 5 flavors with repeats allowed (two scoops of mint, say) is a different count, the one in combinations with repetition.

r runs from 0 to n. For whole numbers with 0 \le r \le n the formula holds. There is no way to choose 6 objects from 4, so the count of such choices is 0, but the formula cannot say so: it would need (4 - 6)! = (-2)!, which does not exist. And \binom{n}{r} for a negative or fractional n or r has no meaning as a count.

Order must truly not matter. If the chosen objects get different roles (a chair and a secretary, first and second place, home and away), swapping two of them changes the outcome and the count is P(n, r), which is r! times larger.

Groups that have no names of their own. Splitting 6 people into a team of 3 and the other 3 looks like \binom{6}{3} = 20 ways, but choosing \{A, B, C\} leaves \{D, E, F\}, and choosing \{D, E, F\} leaves \{A, B, C\}: the same split, counted twice. If the two teams are not told apart (no colors, no names), there are \displaystyle \frac{20}{2} = 10 splits. If one team wears red and the other blue, the 20 is right.

Where this goes next

The numbers \binom{n}{r} sit in a triangle, row n holding \binom{n}{0} up to \binom{n}{n}, and a fact about choosing builds each row from the one above: that is Pascal’s triangle. The same numbers are the coefficients when a sum like (a + b)^n is multiplied out, which is the binomial theorem and the reason \binom{n}{r} is also called a binomial coefficient. Dividing one combination count by another gives the chance of drawing a given number of each kind, as in probability with counting formulas. Allowing repeats leads to stars and bars, and a rule about who may stand where is handled in counting with restrictions. All of it lives under counting.

Exercises

Finding the numbers

  1. Find \binom{7}{2}.
  2. Find \binom{14}{3}.
  3. Find \binom{9}{9} and \binom{9}{0}.
  4. Find \binom{25}{23} without working out any large factorial.
  5. Simplify \binom{n}{2} for a whole number n \ge 2.
  6. Show that \binom{12}{5} and \binom{12}{7} are equal by working out both.

Choosing

  1. A reading list has 15 different books, and a student picks 4 to read over the summer. How many choices are there?
  2. Eighteen points are marked on a circle. How many chords join two of the points?
  3. A lottery draws 6 different numbers from 1 to 40, and the order of the draw does not matter. How many different draws are there?
  4. Eleven points lie on a circle. How many triangles have all three corners at these points?

Does order matter?

  1. Nine people stand for a club’s committee. (a) In how many ways can 2 co-captains with the same role be chosen? (b) In how many ways can a captain and a vice-captain be chosen?
  2. A code is made of 4 different letters of the 26-letter alphabet, in order. How many codes are there? How many different sets of 4 letters do they use?
  3. From 20 vacation photos, 4 are chosen to be printed. How many choices are there? How many ways are there to choose 4 of the photos and show them one after another in a slideshow?

Several groups

  1. A shelf holds 7 different novels and 5 different poetry books. In how many ways can you take 4 novels and 2 poetry books?
  2. A committee of 4 is chosen from 5 teachers and 9 parents. How many committees have exactly 2 teachers?
  3. In the same setting as exercise 15, how many committees have at least one teacher?
  4. A hand of 5 cards is dealt from a standard pack of 52, which has 13 hearts. How many hands are all hearts?

Working backwards

  1. Find the whole number n with \binom{n}{2} = 45.
  2. Find the whole number n with \binom{n}{3} = \binom{n}{5}.
  3. Eight people split into two teams of 4. How many splits are there if the teams have no names? How many if one team wears red bibs and the other blue?

Reasoning

  1. Explain by counting, without the formula, why \binom{n}{r} = \binom{n}{n - r}.
  2. Explain why P(n, r) = r! \binom{n}{r}, and use it to say why P(n, r) is never smaller than \binom{n}{r}.
  3. Explain, both by counting and from the formula, why \binom{n}{0} = 1 and \binom{n}{1} = n.
  4. From n people, a committee of r is chosen and then one committee member is made its chair. Count this in two ways to explain why r\binom{n}{r} = n\binom{n - 1}{r - 1} for 1 \le r \le n.
  5. Explain why \binom{2n}{n} is an even number for every whole number n \ge 1.
Answers
  1. 21. \binom{7}{2} = \dfrac{7 \times 6}{2} = 21.
  2. 364. \binom{14}{3} = \dfrac{14 \times 13 \times 12}{6} = \dfrac{2{,}184}{6} = 364.
  3. Both are 1: one way to take all 9, one way to take none.
  4. 300. By symmetry \binom{25}{23} = \binom{25}{2} = \dfrac{25 \times 24}{2} = 300.
  5. \dfrac{n(n - 1)}{2}. The working form has 2 factors on top, n(n - 1), and 2! = 2 below.
  6. Both are 792. The top of \binom{12}{5} is 12 \times 11 \times 10 \times 9 \times 8 = 95{,}040, and \dfrac{95{,}040}{120} = 792. And \binom{12}{7} = \dfrac{12!}{7!\,5!} is the same fraction.
  7. 1{,}365. The top of \binom{15}{4} is 15 \times 14 \times 13 \times 12 = 32{,}760, and \dfrac{32{,}760}{24} = 1{,}365.
  8. 153. A chord is fixed by its two endpoints, in either order: \binom{18}{2} = \dfrac{18 \times 17}{2} = 153.
  9. 3{,}838{,}380. The working form of \binom{40}{6} has top 40 \times 39 \times 38 \times 37 \times 36 \times 35, which is 2{,}763{,}633{,}600, and bottom 6! = 720. The quotient is 3{,}838{,}380.
  10. 165. No three points on a circle lie on one line, so every 3 of them make a triangle: \binom{11}{3} = \dfrac{11 \times 10 \times 9}{6} = 165.
  11. (a) 36. Swapping the co-captains changes nothing: \binom{9}{2} = 36. (b) 72. The roles differ: 9 \times 8 = 72, which is 2! \times 36.
  12. 358{,}800 codes, using 14{,}950 sets of letters. The codes number 26 \times 25 \times 24 \times 23 = 358{,}800. Each set of 4 letters makes 4! = 24 codes, so there are \dfrac{358{,}800}{24} = 14{,}950 sets.
  13. 4{,}845 choices to print and 116{,}280 slideshows. A slideshow has an order, so it counts 20 \times 19 \times 18 \times 17 = 116{,}280. Each set of 4 photos is shown in 4! = 24 orders, so the prints number \dfrac{116{,}280}{24} = 4{,}845, which is \binom{20}{4}.
  14. 350. \binom{7}{4}\binom{5}{2} = 35 \times 10 = 350.
  15. 360. Exactly 2 teachers means exactly 2 parents: \binom{5}{2}\binom{9}{2} = 10 \times 36 = 360.
  16. 875. All committees: \binom{14}{4} = 1{,}001. No teacher: \binom{9}{4} = 126. So 1{,}001 - 126 = 875.
  17. 1{,}287. The 5 cards are chosen from the 13 hearts. The top of \binom{13}{5} is 13 \times 12 \times 11 \times 10 \times 9 = 154{,}440, and \dfrac{154{,}440}{120} = 1{,}287.
  18. n = 10. \dfrac{n(n - 1)}{2} = 45 gives n(n - 1) = 90, so n^2 - n - 90 = 0, (n - 10)(n + 9) = 0. A count of objects cannot be -9, so n = 10.
  19. n = 8. By symmetry \binom{n}{3} = \binom{n}{n - 3}, and n - 3 = 5 gives n = 8. Directly, in \binom{n}{3} = \binom{n}{5} the left side is \dfrac{n(n-1)(n-2)}{6} and the right side is \dfrac{n(n-1)(n-2)(n-3)(n-4)}{120}. Dividing both by the common factor \dfrac{n(n-1)(n-2)}{6} gives (n - 3)(n - 4) = 20, whose solutions are n = 8 and n = -1, and only 8 is a whole number of objects. Check: \binom{8}{3} = \binom{8}{5} = 56.
  20. 35 splits with no names, 70 with bibs. Choosing the red team is \binom{8}{4} = 70 ways. Without names, each split was counted twice (once from each team), so \dfrac{70}{2} = 35.
  21. Match each choice of r objects with the n - r objects it leaves behind. Different choices leave different objects behind, and every set of n - r objects is left behind by exactly one choice of r (everything else). The matching is one to one, so the two kinds of choice are equally many.
  22. Making an ordered choice of r objects is the same as first choosing which r objects, in \binom{n}{r} ways, then putting them in order, in r! ways whatever was chosen. So P(n, r) = r!\binom{n}{r}. Since r! \ge 1 for every whole number r, P(n, r) \ge \binom{n}{r}, with equality exactly when r! = 1, that is r = 0 or r = 1.
  23. Counting: choosing nothing can be done only one way (the empty set), and choosing one object means naming one of the n. Formula: \binom{n}{0} = \dfrac{n!}{0!\,n!} = 1 because 0! = 1, and \binom{n}{1} = \dfrac{n!}{1!\,(n - 1)!} = n because n! = n \times (n - 1)!.
  24. First way: choose the committee in \binom{n}{r} ways, then its chair from its r members, giving r\binom{n}{r}. Second way: choose the chair first from all n people, then the other r - 1 members from the n - 1 people left, giving n\binom{n - 1}{r - 1}. Both count the same committees with chairs, so they are equal. For example n = 5, r = 2: 2 \times 10 = 20 = 5 \times 4.
  25. The subsets of size n from a set of 2n objects can be paired off, each with the n objects it leaves out, which is again a subset of size n. A subset is never paired with itself, because it and its leftover share no objects and neither is empty when n \ge 1. So the subsets come in pairs, and their number is even. For example \binom{4}{2} = 6 and \binom{6}{3} = 20.
kg1128 · updated 2026-10-19 · CC-BY-SA-4.0