Combination Formula
This page reviews the definition and formula for finding Combinations in mathematics.
Difference between Combinations and Permutations
A combination counts ways to choose a group when order does not matter.
The video contrasts that with permutations:
- permutations count arrangements,
- combinations count subsets,
- permutations care about order,
- combinations do not care about order.
So if the same people are chosen for a team, changing the order of their names does not create a new team.
Watch this section: basic combination definition at 0:00.
Path to 5C3 or $\binom{5}{3}$: Focusing on Notation First
The first problem in the video asks for the number of ways to choose $3$ people from a set of $5$ people.
In the video notation, this is written as $5C3$. This can also be written as $\binom{5}{3}$.
For $5C3$ we are choosing $3$ people out of $5$ people. Each group of $3$ unique people gets counted ONCE!
Watch this section: introduction to the $5C3$ problem at 0:18.
Why The Permutation Count Is Too Big
First lets find $5P3$, the permutation count of how many orders of $3$ people can we make out of $5$ people:
\[5P3=60.\]There are $60$ unique ways we can order $3$ people (think first place, second place, third place) out of $5$ people.
It is useful as a starting point, but it is too large for combinations because the same group of $3$ people can appear in several different orders.
For example, if one group has the same $3$ selected people, those $3$ people can be arranged in
\[3! = 3\cdot 2\cdot 1 = 6\]different orders.
So the permutation list counts each unique group $6$ times.
Watch this section: exploring $5P3$ first at 0:49.
Why We Divide By $r!$ to get from $nPr$ to $nCr$
The reason combinations divide by $r!$ is that every selected subset of $r$ objects can be arranged in $r!$ different ways.
For the video’s $5C3$ example, each group of $3$ people is repeated
\[3! = 6\]times inside the permutation count.
That is why the combination count is
\[\frac{60}{3!}=\frac{60}{6}=10.\]By dividing by how many times each unique group gets repeated in the permutation count we end up with the count of unique subsets of $3$ people.
Watch this section: motivation for dividing by $r!$ at 1:50.
The Combination Formula
The formula for combinations is
\[nCr=\frac{n!}{r!(n-r)!}.\]We can connect it to permutations by dividing by $r!$:
\[nCr=\frac{nPr}{r!}.\]So we (1) start with the number of arrangements then (2) divide by how many ways a unique subset gets counted within the arrangements.
Watch this section: combination formula introduction at 2:38.
First Formula Example: $5C3$
We can now use the formula to find $5C3$:
\[5C3=\frac{5!}{3!(5-3)!}.\]Simplify the denominator:
\[5C3=\frac{5!}{3!2!}.\]Then expand just enough to cancel:
\[5C3=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{(3\cdot 2\cdot 1)(2\cdot 1)}.\]After canceling the repeated factors, the count is
\[5C3=10.\]So there are $10$ ways to choose $3$ people from $5$ when order does not matter.
Watch this section: revisiting the first example with the $nCr$ formula at 3:27.
Second Formula Example: $8C2$
The second example counts ways to choose a $2$ person project team from $8$ students.
Because this is a team, order does not matter. The pair Alice and Jordan is the same team as Jordan and Alice.
Use the formula:
\[8C2=\frac{8!}{2!(8-2)!}.\]Then
\[8C2=\frac{8!}{2!6!}.\]Cancel the $6!$ part:
\[8C2=\frac{8\cdot 7}{2\cdot 1}.\]So
\[8C2=\frac{56}{2}=28.\]There are $28$ ways to pick the $2$ person project team.
Watch this section: start of the $8C2$ problem at 4:19.
Combinations vs. Permutations (Drilling it Home)
Lets put the permutation and combination formula next to each other:
\[nPr=\frac{n!}{(n-r)!}\]and
\[nCr=\frac{n!}{r!(n-r)!}.\]The extra $r!$ in the combination formula deduplicates within every unique subset of $r$ items from the set of $n$ items.
It removes the repeated orders for each subset.
Watch this section: combinations vs. permutations summary at 5:12.
Timestamp Guide
Related Combinatorics Work
Use the companion guide for permutations intro when you want to compare combinations with ordered arrangements.
For the factorial background behind both formulas, use factorials and arrangements.
The video description also points to the JoeCMath combinatorics playlist: watch the playlist on YouTube.