Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

4.1 Combinatorics Helper

Many problems in discrete probability involve counting arrangements. This is especially true for models where outcomes are equally likely, since, when outcomes are equally likely, probabilities are ratios of counts.

We will not emphasize counting problems heavily in this class, so will try to avoid heavy combinatorics. However, there are two counting problems that are so common, we might as well learn the combinatorics. Both involve counting the number of ways we can arrange a list of items. They differ by whether or not the items are distinguishable from each other.

Distinguishable Items

Suppose that you have a list of nn items. For specificity, imagine a list of nn cards. Suppose that the cards are all distinguishable from each other. For example, all the cards have a unique number.

🛠️ How many ways are there to arrange the cards?

Solution

We solved this problem back in Section 1.2 when we wanted to find the chance of drawing two aces in a row from a well-shuffled deck.

Remember, when counting, it is often best to think in sequence.

There are nn options for the first draw. After the first draw, there are n−1n - 1 options. After the first two draws there are n−2n - 2 options for the third. So, repeating the pattern, there are:

n×(n−1)×(n−2)×...3×2×1=n!n \times (n-1) \times (n-2) \times ... 3 \times 2 \times 1 = n!
(1)

So, for any list of nn distinguishable objects, there are always n!n! distinct permutations.

Two Types of Items

What if not all the items can be distinguished?

Then n!n! overcounts, because it counts rearrangements that cannot be distinguished.

For example, suppose that I have five cards. The front side of three of the cards are red, RR, and the front of the remaining two are blue, BB. The back side of the cards are numbered from 1 to 5 so that the red cards are labelled 1, 2, and 3, and the blue cards are labelled 4 and 5.

So, when the cards are front side up, I can’t tell the order of the red cards apart. Nor can I tell the order of the blue cards apart.

In this case, we can list all the possible distinct arrangements:

{RRRBB,RRBRB,RRBBR,RBRRB,RBRBR,RBBRR,BRRRB,BRRBR,BRBRR,BBRRR}\begin{aligned} \{& RRRBB,RRBRB,RRBBR,RBRRB,RBRBR,\\ & RBBRR,BRRRB,BRRBR,BRBRR,BBRRR\} \end{aligned}
(2)

There are 10 possible arrangements. Where did the number 10 come from?

Solution

Here’s a nice argument. Think about each arrangement listed above. For example, think about the arrangement RRRBBRRRBB. This sequence could correspond to any permutation of the cards so that the first three are red. We can spell these out by peaking at the back side of the cards:

FrontRRRBB
Back12345
Back12354
Back13245
Back13254
Back21345
Back21354
Back23145
Back23154
Back31245
Back31254
Back32145
Back32154

Take a careful look at the structure of this table. Notice that, for every order of the red cards there are 2=2!2 = 2! ways to order the blue cards. For every order of the blue cards, there are 6=3!6 = 3! ways to order the red cards.

So, if we fix the order of red and blue cards, then there are 3!×2!3! \times 2! ways to arrange the cards.

Imagine, now, that instead of seeing the front of the cards, you see the back of the cards. Then, you can distinguish all 5, so would be able to distinguish 5!5! distinct sequences. But, those 5!5! sequences can be broken into sets of size 3!×2!3! \times 2!, where all permutations within each set order the colors (front side of the cards) identically.

Therefore, the number of distinguishable arrangements is:

5!3!×2!=(total number of cards)!(number of red cards)!(number of blue cards)!\frac{5!}{3! \times 2!} = \frac{(\text{total number of cards})!}{(\text{number of red cards})!(\text{number of blue cards})!}
(3)

Checking:

5!3!×2!=5×4×3×2×1(3×2×1)×(2×1)=5×42=5×2=10\begin{aligned} \frac{5!}{3! \times 2!} & = \frac{5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)\times(2 \times 1)} \\& = \frac{5 \times 4}{2} = 5 \times 2 = 10 \end{aligned}
(4)

The solution given above is an example of the next combinatorial operator after a factorial.

We usually read a binomial coefficient as nn choose mm. We use the word choose since the binomial coefficient counts the number of ways we could choose mm items from a collection of nn, if we don’t care the order we choose in.

This is one common application of the binomial coefficient. Suppose I have a list of nn names, and want to form a poll group by randomly selecting mm individuals. If I don’t care about the order in which I pick, then every individual is simply assigned to the “picked” class, or the “not picked” class. Choosing mm individuals from all nn is then the same as assigning each individual a PP or a NN. If we list the individuals in order, then each selection is a string of length nn, containing mm letters PP, and (n−m)(n - m) letters NN.

For example, the string NNPNPNNPNP means we formed out poll group by choosing individuals 3 and 5. Then, the number of possible groups is the number of nn letter words made up of mm P’s and (n−m)(n-m) N’s. This is, the number of ways to rearrange a list of objects that are divided into two classes of fixed size, so is the same as the problem we solved above.

Chapters
Appendices