maths.free › Combinatorics & Graph Theory › 4. Counting › Combining Outcomes

Combining Outcomes

Investigation A standard deck of playing cards contains 52 cards. There are four suits: clubs, diamonds, hearts, and spades. Each suit contains cards of 13 values: Ace, 2, 3,..., 10, Jack, Queen, and King.

Section Preview

Investigation

A standard deck of playing cards contains 52 cards. There are four suits: clubs, diamonds, hearts, and spades. Each suit contains cards of 13 values: Ace, 2, 3,..., 10, Jack, Queen, and King.

We call the hearts and diamonds red cards (with clubs and spades the black cards). In each suit, the Jack, Queen, and King are called face cards (the others are call number cards).

Suppose you pick two cards from a deck. How many different combinations will have the first card be a red card and the second card be a face card?

Combinatorics is about counting, but looking at the word, we see it really deals with how things combine. In this section, we will consider two very different ways that we can combine the outcomes we count in combinatorics problems.

What are Outcomes?

Before we start counting, a quick note about how we ask counting problems. Often counting problems are asked terms of how many ways something can happen. That is, there is some event that can result in different outcomes, and it is the different outcomes that are counted. Alternatively, we can take a less active view by asking for the number of elements in a set, such as the set of bit strings of a particular length and weight. However, this too could be rephrased as a question about an event: if you randomly select one of the bit strings (from the set of bit strings), how many things can happen?

So counting the elements in a set or counting the number of outcomes of an event is not really different. Let's think of every counting problem as asking for the number of elements in a set of outcomes.

At the most basic level, counting is not hard at all: Just write all the outcomes in a numbered list and see how many numbers you use. Let me tell you about my bow tie collection. I have,

  1. A purple bow tie.

  2. A green bow tie.

  3. A striped bow tie.

  4. A paisley bow tie.

How many bow ties do I have (how many ways can I select a bow tie)? Well, the largest number in my numbered list is 4, so I have four bow ties.Obviously this example is quite outdated; only four bow ties? What sort of mathematician do you take me for? Of course, as we saw in the previous section, we can use shortcuts to avoid listing out all of the outcomes, such as using Pascal's triangle to find the number of items in our list.

Where counting begins to get interesting is when we want to make a new list that combines two or more lists we have already counted. For example, suppose that in addition to my list of four bow ties, I had a list of seven pairs of novelty socks. I could ask how many choices I have if I wanted to wear either a cool bow tie or a pair of novelty socks. Okay, combine my two lists to make a new list with 11 items: Perhaps first list the four bow ties and then keep counting (starting with 5 for the first pair of socks) until you have listed the seven additional items, ending at 11.

In this example, we have combined our two sets of outcomes (picking a bow tie and picking a pair of socks) to get a new set of outcomes (picking a bow tie or pair of socks). That resulting set of outcomes contained 11 elements.

The difference between the two scenarios is subtle. There are two ways we can think of combining outcomes:

  1. We can combine the sets of outcomes.

  2. We can combine the outcomes in the sets.

Being able to distinguish between these operations is a key skill in combinatorics.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

The Sum and Product Principles

Let's carefully write down the rules we can use to combine sets of outcomes and outcomes in sets.

It is important that the events be disjoint: i.e., that there is no way for \(A\) and \(B\) to both happen at the same time. For example, a standard deck of 52 cards contains \(26\) red cards and \(12\) face cards. However, the number of ways to select a card which is either red or a face card is not \(26 + 12 = 38\). This is because there are 6 cards which are both red and face cards.

Example

How many two-letter words start with either A or B? (A word is just a sequence of letters; it doesn't have to be English, or even pronounceable.)

Solution

First, how many two-letter words start with A? We just need to select the second letter, which can be accomplished in 26 ways. So there are 26 words starting with A. There are also 26 words that start with B. To select a word that starts with either A or B, we can pick the word from the first 26 or the second 26, for a total of 52 words.

We have two sets of outcomes: the words starting with A and the words starting with B. We create a new set of outcomes by combining the sets to get the set of words that start with either A or B, and by the sum principle, this new set contains 52 outcomes.

We often use the principle when the sets of outcomes need to be counted using other counting techniques.

We can also use the sum principle indirectly in a way that might be called the subtraction principle (but isn't).

Example

How many \(10\)-bit strings of weight \(6\) have at least one 1 in their first three bits?

Solution

There are lots of different ways a string can have at least one 1 in its first three bits: It could start with 100, 010, 001, 101, 110, 011, or 111. We could count the number of strings that start with each of them and then apply the sum principle a bunch of times. But let's not.

Suppose the number of strings we want to count is \(x\). Let \(y\) be the number of \(10\)-bit strings of weight 6 that do not have a 1 in any of their first three bits. What is \(x + y\)? This is the number of \(10\)-bit strings of weight 6 in total, which is \(\binom{10}{6} = 210\). It is also easy to find \(y\): Bit strings with length 10 and weight 6 that start with 000 must end in a bit string with length 7 and weight 6. There are \(\binom{7}{6} = 7\) of these.

Thus, we have \[x + 7 = 210\], so \(x = 210 - 7 = 203\).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Combining Principles

Let's return to this section's Investigate! question: How many ways can you select two cards from a standard deck of 52, so that the first one is a red card and the second one is a face card?

This looks a little like the product principle since the outcomes consist of pairs of cards. There are 26 red cards that are outcomes for the first event, and 12 face cards that are outcomes for the second event. However, the answer is not \(26 \cdot 12\). The problem is that while there are 26 ways for the first card to be selected, it is not the case that for each of those, there are 12 ways to select the second card. If the first card was both red and a face card, then there would be only 11 choices for the second card.

In we will explore some ways to adjust for counting problems when events are not disjoint, but we can solve our card problem now if we are careful. Think about the entire set of two-card outcomes. Can we split these outcomes into two disjoint sets (as to apply the sum principle) such that each set can be formed using the product principle?

Of all the outcomes, we first count those that start with a red, non-face card. Of the 26 red cards, there are 6 that are face cards, so there are 20 red, non-face cards. For each of these, there are 12 face cards that can be selected as the second card. By the product principle, the number of two-card outcomes starting with a red, non-face card is \(20 \cdot 12 = 240\).

Now, what outcomes have we not yet counted? It is exactly the two-card outcomes that start with a red face card. There are 6 cards we could start with, and for each there are 11 choices for the second card. So the number of two-card outcomes starting with a red face card is \(6 \cdot 11 = 66\).

Finally, apply the sum principle to these two disjoint sets of outcomes to see that the total number of two-card outcomes is \(240 + 66 = 306\).

We conclude this section with two more examples of how you can use both the sum and product principles in a single counting problem.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (7)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Think about the methods you used to solve the questions about appetizers and entrées. Can you frame these as rules for how to combine two numbers of things when counting? Write down the rules for these methods.

  2. How will you decide if you should add or multiply when combining numbers in a counting problem? Explain how you are currently thinking about this.

  3. Your cousin is trying to solve a counting problem about how many different routes he can take between his dorm and his classroom. He has 9 routes that make sense, and similarly, there are 9 routes to go back from his classroom to his dorm.

    How many round trips are possible? Your cousin says 18, because after going from his dorm to the classroom, he has to add on a route back to the dorm. Is he right? Why or why not?

  4. What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.

  5. Your wardrobe consists of 6 shirts, 3 pairs of pants, and 15 bow ties. How many different outfits can you make?

    答えを明らかにしろ

    By the product principle, there are \(6 \times 3 \times 15 = 270\) different outfits.

  6. Your Blu-ray collection consists of 9 comedies and 7 horror movies. Give an example of a question for which the answer is:

    1. 16.

    2. 63.

    答えを明らかにしろ

    1. For example, 16 is the number of choices you have if you want to watch one movie, either a comedy or horror flick.

    2. For example, 63 is the number of choices you have if you will watch two movies, first a comedy and then a horror movie.

  7. The number 735000 factors as \(2^3 \cdot 3 \cdot 5^4 \cdot 7^2\). How many divisors does it have? Explain your answer using the multiplicative principle.

    答えを明らかにしろ

    Hint:

    For a simpler example, there are 4 divisors of \(6 = 2\cdot 3\). They are \(1 = 2^0\cdot 3^0\), \(2 = 2^1\cdot 3^0\), \(3 = 2^0\cdot 3^1\), and \(6 = 2^1\cdot 3^1\).

Symbols used here

\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
i
imaginary unit
i² = −1.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

How to: Combining Outcomes

  1. Apply the sum and product principles to count the number of outcomes of an event.
  2. Solve counting problems using a combination of the sum and product principles.
  3. Justify the product principle in terms of the sum principle.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

あなた自身を試してみてください

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

ここに Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs