Combination Formula
This page follows the JoeCMath video Combination Formula: Why We Divide by r! | nCr. The video compares combinations with permutations, then shows why the combination formula divides by $r!$.
Main Idea
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.
The 5C3 Setup
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$. In LaTeX, this page writes the same idea as $\binom{5}{3}$.
The key phrase is choose $3$ people. Once the group is chosen, the order inside the group does not matter.
Watch this section: introduction to the $5C3$ problem at 0:18.
Why The Permutation Count Is Too Big
The video first looks at the related permutation count:
\[{}_{5}P_{3}=60.\]That counts ordered arrangements. 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!$
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.\]The division removes repeated arrangements of the same group.
Watch this section: motivation for dividing by $r!$ at 1:50.
The Combination Formula
The video introduces the formula for combinations as
\[\binom{n}{r}=\frac{n!}{r!(n-r)!}.\]It also connects combinations back to permutations:
\[\binom{n}{r}=\frac{\,{}_{n}P_{r}}{r!}.\]This matches the video idea: start with the ordered arrangements, then divide by the number of repeated orders for each selected group.
Watch this section: combination formula introduction at 2:38.
First Formula Example: $5C3$
Now use the formula on the first example:
\[\binom{5}{3}=\frac{5!}{3!(5-3)!}.\]Simplify the denominator:
\[\binom{5}{3}=\frac{5!}{3!2!}.\]Then expand just enough to cancel:
\[\binom{5}{3}=\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
\[\binom{5}{3}=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:
\[\binom{8}{2}=\frac{8!}{2!(8-2)!}.\]Then
\[\binom{8}{2}=\frac{8!}{2!6!}.\]Cancel the $6!$ part:
\[\binom{8}{2}=\frac{8\cdot 7}{2\cdot 1}.\]So
\[\binom{8}{2}=\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
The video ends by putting the two formulas next to each other:
\[{}_{n}P_{r}=\frac{n!}{(n-r)!}\]and
\[\binom{n}{r}=\frac{n!}{r!(n-r)!}.\]The extra $r!$ in the combination formula is the deduplication step. 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.