Combination Notation

(Video) Counting Using Combinations

by PatrickJMT

In this video, by PatrickJMT, Patrick explains combinations and how you use them.

$\large{\text{Summary}}$

Combinations are counting without replacement and the order does NOT matter.

> Suppose you have $n$ objects and you want to select $r$ of those. How many different combinations can you make?

We use a special combination notation to represent the sentences above. All three of them mean the same thing: "$n$ choose $r$." $$_nC_r=C_r^n=\binom{n}{r}$$

All of these refer to the same equation: $$\boxed{=\frac{n!}{(n-r)!r!}}$$

Example 1

The first example Patrick looks at is: $$_5C_2=$$

This is pretty straightforward to solve. We just use the formula and plug $n$ and $r$. So, "$5$ choose $2$" is equal to: $$\begin{align} \frac{n!}{(n-r)!r!}&=\frac{5!}{(5-2)!2!}\\\ &=\frac{5!}{3!2!}\\\ &=\frac{5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\cdot2\cdot1}\\ &=\frac{5\cdot4\cdot\color{red}{3}\cdot\color{red}{2}\cdot\color{red}{1}}{\color{red}{3}\cdot\color{red}{2}\cdot\color{red}{1}\cdot2\cdot1}\\ &=\frac{5\cdot4}{2\cdot1}\\ &=\frac{20}{2}\\ &=10 \end{align}$$ This tells us that if we have $5$ objects and we only choose $2$ of them, there are $10$ combinations!

Example 2

Next, up is the dreaded word problem! > Suppose $10$ horses run a race; you would like to know in how many ways $3$ horses can finish in 1st, 2nd, and 3rd in any order.

Let's think about this. Suppose horses $A$, $B$, and $C$ come in the first three places respectively. Because we're looking for the combinations, order doesn't matter. That means if horses $B$, $C$, and $A$ come in the first three places respectively it's still considered the same combination because we still have the same three horses.

So we set up our combination problem as follows: $$\begin{align} _{10}C_3&=\frac{10!}{(10-3)!3!}\\ &=\frac{10!}{7!3!}\\ &=\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1\cdot3\cdot2\cdot1}\\ &=\frac{10\cdot9\cdot8\cdot\color{red}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}}{\color{red}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}\cdot3\cdot2\cdot1}\\ &=\frac{10\cdot9\cdot8}{3\cdot2\cdot1}\\ &=\frac{720}{6}\\ &=120 \end{align}$$ There are $120$ different options for the horses.

Example 3

This one is a little trickier. > You're playing poker. How many 5-card poker hands consisting of $3$ aces and $2$ cards that are not aces are possible with a $52$ card deck?

We need to find two different combinations and then add them together. The first combination is choosing the $3$ aces. A standard deck has $4$ aces. So our combination becomes: $$_4C_3$$ Next we need to choose two non-aces. A standard deck has $52-4=48$ non-aces. So our combination becomes: $$_{48}C_2$$ Multiplying these together gives us the different combinations of hands. $$\begin{align} _4C_3\times _{48}C_2&=\frac{4!}{(4-3)!3!}\times\frac{48!}{(48-2)!2!}\\ &=\frac{4}{1}\times\frac{48\cdot47}{2\cdot1}\\ &=4\times1128\\ &=4512 \end{align}$$

Combinations

The first thing to know about combinations is that they are not the same thing as permutations.

I'm going to include a few of the comparisons and examples that you can also find in my permutations explanation here. I think they do a pretty good job of illustrating how the two concepts are different.

With combinations, order doesn't matter. Jaya, Zach, and Marlee is the same as Zach, Marlee, and Jaya. Either way, it's the same combination of people.

With permutations on the other hand, order matters. Jaya, Zach, and Marlee is a totally different permutation than Marlee, Jaya, and Zach.

Here's another example, based on a joke that math teachers like to tell:

Here's another example that might help.

When we're trying to come up with permutations, the order of the scoops matters. However, when we're talking about combinations, order doesn't matter.

Whether you start with strawberry, chocolate, or vanilla, you have the same combination of 3 flavors no matter how you stack the scoops.

Here's the formula and notation you'll need to use to officially figure out the number of combinations you've got:

$$_nC_r = \frac{n!}{r!(n - r)!}$$

In math, an exclamation point is the symbol for a factorial. Scroll down in the explanation linked here to see what factorials are.

Let's work through an example to see how to calculate combinations.

Here's the formula again:

$$_nC_r = \frac{n!}{r!(n - r)!}$$

$$_7C_3 = \frac{7!}{3!(7 - 3)!}$$

(Video) The Counting Principle, Permutations, and Combinations

by Jack Walker

Jack Walker has a great video on the multiplication counting principle, permutations, and combinations.

$\large{\text{Summary}}$

The first part of the video details the multiplication counting principle. Then it moves into permutations, and finally combinations. Great emphasis is placed on the differences between permutations and combinations. On that note we present a conceptual question to drive that point home. Feel free to re-watch the video as many times as you'd like.

COMBINATIONS

Combinations are very similar to permutations as they are also trying to find how many smaller groups can be made out of a larger set of elements. Just like how permutations have permutation notation, combinations have combination notation: $$_n C_r$$ Where $n$ is the number of elements in the overall set, and $r$ is the number in each group that you’re trying to calculate. Once again, $n$ will always be the larger number. The equation for combinations is very similar to permutations, but with one extra step: $$_n C_r =\frac{n!}{\left(n-r\right)!\cdot r!}$$ In the denominator, you multiply $(n-r)!$ by $r!$ . This is the only part that is different in this equation compared to the one for permutations.

Let’s run through a problem just to understand the use of this equation.

In music, a triad is defined as any combination of $3$ notes. Between each octave on a keyboard there are $12$ different notes that can be played. How many different chords could be played within one octave?

In this case $n = 12$ notes per octave, and $r = 3$ notes in each triad. $$_{12} C_3=\frac{12!}{(12-3)!\cdot3!}=\frac{12!}{9!\cdot3!}$$ Once again, break each factorial into its own factors, and cancel out factors that are on both sides. $$\begin{align}\frac{12!}{9!3!} &=\frac{12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1\cdot3\cdot2\cdot1} \\ &=\frac{12\cdot11\cdot10}{3\cdot2\cdot1} \\ &=\frac{1320}{6} \\ &=\boxed{220}\end{align}$$ The denominator shows $9!$ immediately followed by $3!$. There is no need to separate them as each factor is being multiplied. In this problem, the $(3\cdot2\cdot1)$ from $3!$ cancels out with the same set from the $12!$ in the numerator, as does $(9\cdot8\cdot7\cdot6\cdot5\cdot4)$ from $9!$, but there is still $(3\cdot2\cdot1)$ left over at the end. This is because that set of numbers is repeated in the denominator, but not in the numerator, and therefore will not get cancelled out.

If you're still a little uncomfortable with the idea, here is a video that goes over both Permutations and Combinations in depth by Brandon Foltz on YouTube.