Combinations

In one sentence: A combination counts the different groups you can pick from a set of items when the order of the picks does not matter.

$C(n,k) = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}$

Read it out loud: “C of n, k, also written n choose k, equals n factorial, divided by k factorial times n minus k factorial. Here n is the total number of items you can pick from, and k is how many you pick. The order of the picks does not matter, so the answer counts groups, not lists.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Factorial, $n!$: $n!$ is read ‘n factorial’. It means multiply $n$ by every whole number below it, down to 1: $4! = 4 \times 3 \times 2 \times 1 = 24$ . A factorial counts orders, the number of ways to line up $n$ different items in a row. By convention $0! = 1$ , which means there is exactly one way to line up nothing.
Ordered and unordered: Ordered means the sequence matters, like first place and second place. Unordered means only the chosen items matter, like the members of a team. Ana, Ben and Cy form the same team in any order. Combinations are unordered, and permutations are ordered.
Binomial notation $\binom{n}{k}$: $\binom{n}{k}$ is read ‘n choose k’. The stacked numbers show the total $n$ on top and the number picked $k$ below. It counts the groups of $k$ items you can choose from $n$ items. Another name for this count is the binomial coefficient, and it is the same number that appears in Pascal’s triangle.
Canceling factors in a fraction: A fraction with factorials often simplifies, because the same factors appear on the top and the bottom. In $\frac{5!}{3!\,2!}$ , the factors 3, 2 and 1 in $3!$ cancel against the same factors in $5!$ . What is left is $\frac{5 \cdot 4}{2 \cdot 1} = \frac{20}{2} = 10$ .
Pascal’s triangle (background): Pascal’s triangle is a pattern of numbers in rows, where each number is the sum of the two numbers above it. The row for $n = 5$ reads 1, 5, 10, 10, 5, 1. Those numbers are the combinations $\binom{5}{0}, \binom{5}{1}$ up to $\binom{5}{5}$ , so the triangle is a table of combinations.

What each symbol means

Symbol	Meaning
$C(n,k)$	The number of combinations, read ‘n choose k’. It counts groups, so it has no unit. The same number is also written $\binom{n}{k}$ . For 5 friends and a team of 3, $C(5,3) = 10$ different teams.
$n$	The total number of items you can pick from, a whole number 0 or more. For example, $n = 5$ means there are five friends to choose from. Every item can be picked once, and the count has no unit.
$k$	The number of items you pick for the group, a whole number from 0 to $n$ . For a team of three friends, $k = 3$ . It counts the members of the group, not the order in which they were picked.
$n!$	The factorial of $n$ , the product of every whole number from $n$ down to 1. For example $4! = 24$ , and by convention $0! = 1$ . It counts the ways to line up $n$ items in a row, so it has no unit.

The formula piece by piece

$n$: The total number of items you can choose from. In the team example, $n = 5$ friends. Every friend is available to pick once, so $n$ counts the whole pool of people, toppings or cards.
$k$: How many items you pick for the group. Here $k = 3$ , a team of three. It is a whole number from 0 up to $n$ , and it counts the members of the group, not the order they were picked in.
$k!$: The number of ways to line up the $k$ picked items. Each group of $k$ items appears this many times in the ordered count, so dividing by $k!$ removes the repeats. For a team of 3, $3! = 6$ .
$(n-k)!$: The factorial of the items you leave out. When $n!$ is divided by $(n-k)!$ , the factors for the leftover items cancel, and only the $k$ spots remain. This gives the count of ordered picks, before the repeats are removed.
$C(n,k) = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}$: In one plain sentence: the number of groups of $k$ items you can pick from $n$ items, where order does not matter, equals $n$ factorial divided by $k$ factorial times $(n-k)$ factorial.

What the formula is doing, and why

What goes in and what comes out. You put in $n$ , the number of items you can choose from, and $k$ , the number you want in the group. You get out a whole number of different groups. The result has no unit, because it counts groups. Picking Ana and then Ben gives the same group as picking Ben and then Ana, so only one of those counts.

Why divide by $k!$ ? Start with the ordered case. The first pick has $n$ choices, the second has $n-1$ , and so on down to $n-k+1$ for the last pick. That gives $\frac{n!}{(n-k)!}$ ordered picks. But each group of $k$ items shows up in $k!$ different orders, so the ordered count repeats every group $k!$ times. Dividing by $k!$ removes those repeats, which leaves $\frac{n!}{k!\,(n-k)!}$ .

Why do the factorials make sense? The $(n-k)!$ part cancels the factors for the items you did not pick. A useful fact follows from the formula: $\binom{n}{k} = \binom{n}{n-k}$ . Choosing the $k$ items you want is the same as choosing the $n-k$ items you leave out, so both choices give the same count.

When should you use it? Use combinations when a group matters and a list does not, such as a team, a set of toppings or a poker hand. When the order does matter, for example for first, second and third place, use permutations instead. For the same $n$ and $k$ , permutations always give at least as many answers, because each group can be ordered in $k!$ ways.

Edge cases. If $k = 0$ , there is exactly one way to pick nothing, and the count is 1. If $k$ is bigger than $n$ , there are no groups at all, so the count is 0.

An everyday picture

Think of picking a team of three friends from five for a board game. Ana, Ben and Cy is the same team as Cy, Ben and Ana, so the order you chose them in does not count. A combination counts the teams, not the orders in which each team was picked. There are 10 different teams, even though there are 60 ordered ways to make the picks.

Worked example: Picking a team of 3 from 5 friends

You have 5 friends and want a team of 3 for a board game. The order you pick them in does not matter, so we want the number of combinations $C(5, 3)$ , read ‘5 choose 3’. Name the friends A, B, C, D and E to follow the steps.

Count the ordered picks. The first pick has 5 choices, the second has 4 left, and the third has 3 left. So there are $5 \cdot 4 \cdot 3 = 60$ ordered picks. This count treats ‘first Ana, then Ben, then Cy’ and every other order as separate picks.
Count the orders inside one team. A team of 3 people can be lined up in $3! = 3 \cdot 2 \cdot 1 = 6$ ways. So each team of three shows up 6 times among the 60 ordered picks.
Divide out the repeats. Every team is counted 6 times, so divide the ordered count by 6. That gives $C(5,3) = \frac{60}{6} = 10$ teams.
Check with the formula. The standard formula for combinations gives the same answer. Compute the factorials first: we have $5! = 120$ , $3! = 6$ and $2! = 2$ , so the value is $\frac{120}{6 \cdot 2} = \frac{120}{12} = 10$ . Both methods agree.
List the teams to see the result. The 10 teams are ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE and CDE. Each team is written once, in alphabetical order, so no team is counted twice.
Notice the symmetry. Choosing the 3 people for the team is the same as choosing the 2 people who stay off it. So $C(5,3) = C(5,2) = \frac{5 \cdot 4}{2 \cdot 1} = 10$ , which matches the count.

Answer: There are 10 different teams of 3 friends. The ordered count of 60 is six times too big, because each team appears in six different orders.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Counting order. Ana then Ben and Ben then Ana are one combination, not two. If your count is about $k!$ times too big, you have counted the orders.
Letting $k$ be bigger than $n$ . You cannot pick 4 items from 3, so the number of groups is 0.
Mixing up combinations and permutations. A race with first, second and third place needs permutations, because the order of finish matters.
Forgetting that $0! = 1$ . It matters for $C(n,0) = 1$ and $C(n,n) = 1$ : picking nothing, or picking everything, each has exactly one answer.

Where you will meet it

Counting poker hands and lottery draws, where the cards or numbers in one hand or draw form a group, not a list.
Choosing toppings, side dishes or committee members when the order of choosing does not matter.
Probability, which is a number from 0 (never) to 1 (always) that says how likely something is. The chance of an event is the number of favorable groups divided by the number of all possible groups.
Pascal’s triangle and the binomial theorem, where the numbers $\binom{n}{k}$ are the coefficients of $(a+b)^{n}$ . A coefficient is the number in front of a term, so $(a+b)^{2} = a^{2} + 2ab + b^{2}$ has coefficients 1, 2 and 1.

Questions people ask

What is the difference between combinations and permutations?

A permutation counts ordered arrangements, such as first, second and third place. A combination counts groups where the order is ignored. For the same $n$ and $k$ , the permutation count is $k!$ times the combination count. For 8 runners and 3 places, that is $336 = 6 \times 56$ .

Why do the factorials always give a whole number?

Every group is counted $k!$ times in the ordered count, so dividing by $k!$ leaves exactly one count per group. A count of groups must be a whole number, so the result is always whole.

What are $C(n,0)$ and $C(n,n)$?

Both equal 1. There is exactly one way to pick nothing, and exactly one way to pick everything. For example, $C(5,0) = \frac{5!}{0!\,5!} = 1$ .

Permutations: A permutation is one way of picking some items and lining them up in a set order, and this formula counts how many such lineups exist.
Inclusion-Exclusion Principle: Inclusion-exclusion counts how many items belong to at least one group by adding the groups and then removing the overlaps that were counted twice.
Pigeonhole Principle: If you put more things than boxes into the boxes, at least one box must hold two or more things.