One of the first bits of mathematical knowledge children learn is how to count objects by pointing to them in turn and saying: “one, two, three, …” That’s a useful skill, but when the number of things that we need to count grows large, that method becomes onerous (or, for very large numbers, impossible for humans to accomplish in a typical human lifespan). So, mathematicians have developed shortcuts for counting big numbers. These techniques fall under the mathematical discipline of combinatorics, which is devoted to counting.

Multiplication as a Combinational Shortcut

One of the first combinatorial shortcuts to counting students who learn in school has to do with the areas of rectangles. If we have a set of objects to be counted that can be physically arranged into a rectangular shape, then we can use multiplication to do the counting for us. Consider this set of objects in Figure 7.3.

Certainly we can count them by pointing and running through the numbers, but it’s more efficient to group them (Figure 7.4).

If we group the balls by 4s, we see that we have 6 groups (or, we can see this arrangement as 4 groups of 6 balls). Since multiplication is repeated addition (i.e., ), we can use this grouping to quickly see that there are 24 balls.

Let’s generalize this idea a little bit. Let’s say that we’re visiting a bakery that offers customized cupcakes. For the cake, we have three choices: vanilla, chocolate, and strawberry. Each cupcake can be topped with one of four types of frosting: vanilla, chocolate, lemon, and strawberry. How many different cupcake combinations are possible? We can think of laying out all the possibilities in a grid, with cake choices defining the rows and frosting choices defining the columns (Figure 7.5).

Since there are 3 rows (cakes) and 4 columns (frostings), we have possible combinations. This is the reasoning behind the Fundamental Counting Principle, which is also known as the Multiplication Rule for Counting.

This principle says that: if there are ways to accomplish one task and ways to accomplish a second task, then there are ways to accomplish both tasks.

We can tack on additional tasks by multiplying the number of ways to accomplish those tasks to our previous product.

Example 1

Every card in a standard deck of cards has two identifying characteristics: a suit (clubs, diamonds, hearts, or spades; these are indicated by these symbols, respectively: , , , ) and a rank (ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, and king; the letters A, J, Q, and K are used to represent the words). Each possible pair of suit and rank appears exactly once in the deck. How many cards are in the standard deck?

Show / Hide Solution

Since there are 4 suits and 13 ranks, the number of cards must be (Figure 7.6).

 

The Fundamental Counting Principle Involving Restrictions

When solving problems, it is important to deal first with restrictions.

2.1 Exercise Set

1. A website that lets you build custom belts has 18 different buckles and 30 different straps. How many different belts can be made using those materials?
2. A chain of chicken restaurants offers a combo that includes your choice of 3 or 5 chicken strips, along with your choice of side dish. If there are 7 side dishes, how many different ways are there to build this combo meal?
3. When you flip a coin, there are 2 possible outcomes: heads and tails. Let’s say you flip a coin 10 times, and after each you write down the result of the flip (H for heads, T for tails). How many different results (strings of 10 characters, where each is either an H or a T) are possible?
4. A T-shirt company allows shoppers to customize their shirts in several ways. There are 5 sizes, 8 shirt colors, 4 designs, and 5 design colors. How many different shirts can be made?
5. Josephine is trying to build her class schedule for next semester. Because of her work schedule, she has only 4 class periods that can work for her, and she must take 4 classes. If there are 15 classes that she could take during the first period, 18 during the second, 12 during the third, and 8 during the fourth, how many different schedules could Josephine build?
6. An ice-cream parlor sells 26 different flavors of ice cream. A basic sundae has one scoop of any flavor of ice cream, your choice of one of 3 sauces, and any one of 8 different toppings.How many different basic sundaes are possible?
7. A company that builds custom computers offers 4 hard drive sizes, 4 memory sizes, 3 graphics cards, and 3 display options. How many computer configurations do they offer, if customers choose one of each customization?
8. A video game allows users to customize their avatars. There are 12 hair styles that users may choose from, as well as 5 hair colors, 8 skin tones, 24 shirts, 12 pants, and 8 shoes. How many different avatars are possible?
9. A small company has 3 divisions: Sales, Research and Development, and Manufacturing. One person from each division will be chosen to create an advisory board for the management group. If there are 8 people in Sales, 15 in Research and Development, and 48 in Manufacturing, how many different compositions of the advisory board are possible?
10. A multiple-choice quiz has 5 questions, each of which has 4 possible answers. How many different ways are there to respond to this quiz?
11. The teacher decides to make the quiz from above a little harder by offering 5 responses on each of the 5 questions. How many ways are there to respond to this quiz?
12. In the United States, radio and television broadcast stations are assigned unique identifiers known as call signs. Call signs consist of 4 letters. The first is either K or W (generally speaking, stations with a K call sign are west of the Mississippi River and stations with a W call sign are east of the river, though there are several exceptions to this rule); the remaining 3 letters can be anything. How many possible call signs are there under this system?
13. Little sister has asked big brother to play a new game she’s invented. It uses a modified deck of cards with 3 suits and only the numbered cards (those with rank 2 through 10). How many cards are in her deck?
14. The board game Mastermind has 2 players. One of them is designated the codemaker who creates a code that consists of a series of 4 colors (indicated in the game with 4 colored pegs), which may contain repeats. The other player, who is the codebreaker, tries to guess the code. If there are 6 colors that the codemaker can use to make the code, how many possible codes can be made?
15. How many arrangements are possible of the word THURSDAY, if
    1. any letter can be in any position
    2. the first letter must be D
    3. the R is first and H is last
16. How many arrangements are possible of the word FORMULA, if
    1. any letter can be in any position
    2. the first letter must be R
    3. the vowels must be together
17. How many different four-letter arrangements are possible of the word ANOTHER, if
    1. any letter can be in any position
    2. the first letter must be R
    3. the first and last letters must be vowel

2.1 Answers

1. 18×30=540
2. 2×7=14
3. 2x2x2x2x2x2x2x2x2x2=1024
4. 5x8x4x5=800
5. 15x18x12x8=25920
6. 26x3x8=624
7. 4x4x3x3=144
8. 12x5x8x24x12x8=1105920
9. 8x15x48=5760
10. 4x4x4x4x4=1024
11. 5x5x5x5x5=3125
12. 2x26x26=35152
13. 3×9=27
14. 6x6x6x6=1296
15. (1) 8!=40,320,  (2) 7!=5,040, (3) 6!=720
16. (1) 7!=5040, (2) 6!=720, (3) 5!×3!=120×6=720. 
17. (1) 7⋅6⋅5⋅4=840, (2) 6⋅5⋅4=120, (3) 3×2×5×4=120

Attribution

Text Attribution

This text was adapted from Chapter 7. of Contemporary Mathematics, textbooks originally published by OpenStax.