Development
John wishes to wear a nice pair of dress pants with a sport-coat when he goes out on his first date tonight. He has 5 different pairs of dress pants and 3 different sport-coats. John, wishing to make the best possible first impression, decides to try on each combination of a pair of dress pants and a sport-coat. After trying all of these combinations, he will decide which is the best. It will take him approximately five minutes to get dressed, look carefully at the jacket-pants combination, and then get undressed. If it is 5:30 p.m. now, and John wishes to be leaving his house by 7:00 p.m., will he make it? It’s not hard to see that John should be interested in the number of jacket-pants combinations that he will be trying on. Determining this number is in the realm of an area of mathematics known as combinatorics.
How many jacket-pants combinations will John have to try?
Write down as many different ways of determining the answer to Problem 1 as you can think of. Compare these ways to the ways of other students in your class. Which method is most visual? Least visual?
John’s situation is one that can be reasonably solved by listing all of the possible combinations. This approach, while sufficient, is not particularly useful with the task that Imelda Marcos would have had. She reputedly had approximately 3000 pairs of shoes, 2000 designer dresses, 500 bras, and 200 girdles.
How many shoes-dresses combinations did Imelda have?
How many shoes-dresses-bras combinations did she have?
Can you reasonably answer either Problem 3 or 4 by visualizing? What method(s) used to solve John’s problem can be used with Imelda’s?
Suppose you were trying to determine the number of combinations of ${n_1}$ things combined with ${n_2}$ things combined with ${n_3}$ things and so on up to ${n_k}$ things. How many combinations are there?
The result you probably wrote in Problem 6 is known as the Multiplication Principle of Counting.
Practice
How many dress and girdle combinations did Imelda Marcos have?
You can make a sundae at I Scream by choosing one scoop of ice cream from 6 options (vanilla, chocolate, strawberry, banana, cherry, or coffee), one topping from 4 options (hamburger crumble, pickle pieces, bacon bits, or onion O’s), and one sauce from 3 options (ketchup, mayonnaise, or balsamic). How many different sundaes do you get to choose from? Mmmm!
Going Further
John’s and Imelda’s problems led to our first significant idea in combinatorics. If this was all there were to combinatorics, however, the subject would not be of much interest to mathematicians, computer scientists, or businesses, nor would this lesson have more pages in it (as you can plainly see that it does). Let’s look at some different situations from what we saw before.
The members of the Math Society wish to appoint a slate of officers that will be in charge of its meetings and activities this year. The slate will have 2 positions — President and Secretary. If there are 5 students in the Math Society, how many distinct slates can be formed? By distinct we mean to distinguish the slate consisting of Sheila (President) and Jack (Secretary) from the slate consisting of Jack (President) and Sheila (Secretary). You might think about visualizing in order to get a handle on how to count in this situation.
Suppose that the slate had 3 positions — President, Secretary, and Treasurer — and there were 6 students in the Math Society. How many distinct slates can be formed now?
Suppose that the Math Society expanded to 25 students and, therefore, decided that the governing body should have 4 positions — President, Vice-President, Secretary, and Treasurer. How many distinct slates can be formed now?
In how many different ways can Elsa arrange 5 books on the top shelf of her bookcase? She’s going to arrange them side-by-side and standing up.
In how many different ways can Elsa arrange 20 books on the top shelf of her bookcase? Show your work.
Your response to determining the exact amount in Problem 13 might be to scream as you realize that you will have to write
$20 \cdot 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1.$
Fortunately, Christian Kramp in 1808 showed some foresight and decided to co-opt the exclamation mark for just this situation. Given the above problem, Christian would have written $20!$. (“$20!$” is read as “20 factorial.”)
Write $9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ using factorial notation. Write $6!$ without factorial notation.
Suppose we are going to create a 7-letter “word” by using the letters in the word “numbers”. The “word” doesn’t have to make sense.
How many different 7-letter words can we create if a letter cannot be used more than once in a word? Can you write your answer using factorial notation?
How many different 7-letter words can we create if a letter can be used more than once in a word? Can you write your answer using factorial notation?
What is the probability that a random 7-letter word created from the letters from “numbers”, where each of the letters could be used more than once, also happens to be a 7-letter word that uses each of the letters in “numbers” exactly once?
Problem 15 Part a could have been written using different, but equivalent, language. A common way of expressing this problem is to ask, “How many different 7-letter words can we create if repetition is not allowed?” The phrase “repetition is not allowed” means in this case that a letter cannot be used more than once in a word. Problem 15 Part b, similarly, could have been written, “How many different 7-letter words can we create if repetition is allowed?” Paying attention to whether repetition is allowed is critical when trying to understand what you are trying to count. In other words, you need to develop the habit of re-examine the problem if you’re going to avoid undercounting or overcounting.
Practice
In how many ways can 6 people line up for a movie?
How many four-letter “words” can be made from the letters A, B, C, D, and E, if any arrangement is counted as a “word” and repetition is not allowed? Now consider using the 26-letter alphabet — how many 4-letter words are possible if, again, repetition is not allowed?
How many distinct license plates can be created in a state that has a 6-digit license plate (that is, plates have 6 digits and no letters) where digits can repeat? How many more license plates would there be if a 7th digit was added?
In the picture below, each cylinder is placed in a section of the key. The depth of the section is the “cut”. If you have a key with 6 sections and each can contain one of four different cuts, how many different key configurations are possible?
Over the summer vacation, a student wants to read 14 books. In how many different orderings can the student arrange these books for reading?
In the upcoming school election, a completed ballot is one in which a student has voted for one person for president, one person for vice-president, one for treasurer, and one for secretary. If there are 5 people running for president, 4 for vice-president, 4 for treasurer, and 3 for secretary, how many distinct, complete ballots could be filled out?
Problems
In each problem you should think very carefully about the information that’s been presented in order to determine what is relevant in solving the problem. Furthermore, you should consider visualizing — not necessarily with a tree diagram, but with slots or boxes — as a way of trying to organize the information. Lastly, if the numbers in the problem are large, don’t be afraid to change them to smaller numbers and, therefore, make the problem a little easier to work with initially. By doing this, you are using or developing an important habit called change or simplify the problem.
Three-digit area codes on phones were introduced after it became clear that the restrictions on the seven-digit phone number limited the number of phones that could be in use. The original restrictions on these three-digit codes were as follows: the first digit can only be a digit from 2-9; the second digit must be 0 or 1; and the last can be any digit.
How many area codes were possible?
How many area codes began with the digit 4?
What is the probability that a random area code begins with the digit 4? What is the probability that it does not begin with a 4?
How many area codes ended with a 9?
What’s the probability that a random area code forms an odd number?
In the United States, radio and television stations all have three- or four-letter “call signs” that begin with either K or W. Stations east of the Mississippi River start with W, and stations west of the Mississippi start with K.
In 1928 there were 677 radio stations (and 0 television stations) in the United States. If repetition of letters were allowed (so a station could be called WOW, for example), would it have been possible for each of these stations to have a three-letter call sign?
Today, using three- or four-letter call signs, how many TV or radio stations total could exist east of the Mississippi if repetition of letters were not allowed?
Of all the possible 3-letter call signs, what is the probability that if you randomly choose one it will have all of its letters in common with the station WJZ? For example: WJJ or WWZ.
Of all the possible 4-letter call signs, what is the probability that if you randomly choose one it will have exactly three of its letters in common with WTMD? (For example: KTMM.) How about four letters in common?
How many 3-digit numbers can be made from the digits 1 through 8 with no repetitions? What’s the chance that one of these numbers will be divisible by 5?
A standard combination lock has a three number combination. Each number is in the range 0 to 49 and the order of the numbers matters — i.e., the combination 26-32-7 is different from 7-32-26. How many distinct combinations are there?
The rule IceCream takes the number of kinds of ice cream a store sells, $n$, and outputs the number of triple-scoop ice-cream cones they can possibly make. It counts in such a way that it matters which flavor is on the top or bottom, and multiple scoops with the same flavor are allowed. Write a formula for $IceCream(n)$ = _____________.
Suppose you were going to take a 20-question true-false exam. How many possible arrangements of responses are there? An arrangement in this case is a sequence of T’s and F’s that corresponds to how you answered the 20 questions.
To get onto computers, there are usually passwords required. Suppose your computer requires a 5-character code with the first three characters being digits (0-9) and the last two being letters from the alphabet.
How many codes are there?
If trying each password would take 5 seconds, how long would it take to try all of them?
If you were told that there weren’t any vowels used in the password, how would this affect the amount of time it would take you to try all possible passwords? Also, what is the probability that a password chosen randomly does not have any vowels?
Would it take less time than in Part c if the 3-digit number were even and any of the letters of the alphabet could be used?
The symbol $\circleddash$ takes any integer from 1 to 10 and gives back an integer from 2010 to 2014. How many different rules like this — using these same inputs, and giving as outputs any integer between 2010 and 2014 — could there be?
In Problems 30-33, you’re going to need to think carefully about the given information and then decide how best to prove your answer. You should be prepared to give a step-by-step explanation that would convince any of your classmates. While each of the problems does involving counting, you’ll need to decide whether the Multiplication Principle of Counting is to be used.
Show that in any group of five people, there are two people who have an identical number of friends within the group.
Daryl says that there are 210 possible 3-person committees that can be formed from 7 people. Alecia disagrees, saying that there are only around half that many. What do you think?
Do you have a better chance of getting a sum of 7 with two standard dice or with three?
Suppose that a class of 15 students is asked to shade one quarter of the area of the rectangle shown below. Only whole squares can be shaded, and the shaded squares cannot share a side. Can each student provide an answer that no one else in the class provides?
A bag contains all the rectangles with perimeter 36 whose dimensions are positive integers. If a rectangle is chosen at random from this bag, what are the chances that it will be a square?
Marbles are placed in a hat in a ratio of two red marbles to three blue marbles to five green marbles.
What is the probability that a marble you choose will be red or blue?
If there are 180 marbles in the hat, how many of the marbles are blue?
How many terms are possible when the following product is multiplied out: $\left( {a + b} \right)\left( {c + d} \right)\left( {e + f} \right)$?
You can think of the factorial symbol, !, as taking inputs and outputs, as is the case with many other symbols you’ve encountered.
For which values of $n$ does $n!$ have odd outputs?
For which values of $n$ does $n!$ have outputs that are multiples of six?
Rewrite as simply as possible.
$\frac{x!}{(x-1)!}$
$\frac{x! \cdot x!}{x^2}$
$\frac{x!}{(x+2)!} \cdot (x^2 + 3x + 2)$
Which of the following is $x(yzw)$ equal to? Answer all that are correct:
$(xy)(zw)$
$(xy)(xz)(xw)x$
$xy + xz + xw$
$xyzw$
$zxwy$
$y(zxw)$
Without a calculator determine which is bigger.
$2^{100}$ or $100^2$
$2^{100}$ or $100!$
$100!$ or $50! \cdot 50!$
$100!/50!$ or $60!/30!$
Exploring in Depth
9 girls and 8 boys are standing in a lunch line.
How many ways can they line up if all the girls are first, followed by the boys? Can you write this answer using factorials?
(Part a continued) What’s the chance this will happen? Can you write this answer using factorials?
How many ways can they line up if they alternate gender? Can a boy be first in line? Can you write this answer in terms of factorials?
Don’t use a calculator for this problem.
Simplify $(4x+1)\cdot 2 - x$
Factor ${x^2} - 19x + 84$
Factor $24{x^2} - 48x$
Find $\frac{{14}}{5} + \frac{4}{{15}}$
We can use the symbol $r(x)$ to mean “the reciprocal of $x$.” Find $x$ if $r(x) = r(4) + r(6) + r(12)$.
Without determining what the explicit value is of $10!$, how would you argue that $10! + 10! \ne 20!$? Is it ever the case that $k! + k! = (2k)!$?
The US Open Tennis Championship for women involves a single elimination tournament starting with 64 players (single elimination means that once you lose you’re eliminated from the tournament).
How many tennis matches are played in the tournament?
Is it possible to run a single- elimination tournament with less than 64 players, if no player is allowed a “bye”? If so, what number of players can participate in such a tournament? If not, explain why.
Suppose the tournament was double-elimination — two losses and you’re eliminated. How many matches are played in this tournament?
In Morse code, there are two symbols — a dot and a dash. Since there are 26 letters in the alphabet, there would have to be 26 different configurations of dots and dashes to use the Morse code successfully. Will any of the letters require a configuration with a total of five dots and/or dashes? Why?