- Professor Shai
Counting is part of an area
of mathematics called combinatorics which is getting more airplay
nowadays at all levels of education. Combinatorics is intimately
tied up with probability, because to calculate many probabilities, you
need to count. There are four major tricks that you will
learn on this page. Each will be illustrated with an
- This or That.
This is maybe too simple to call a trick. Let's say you have 5
shirts that you wear in the summer, and your mom buys you 3 new
shirts. How many different ways are there to choose either one of
the 5 shorts or one of the 3 shirts? You have 8 total shirts, so
there are 8 ways. In general, when you see "or" you can think
Multilplying - This and That.
Let's say you have 5 shirts and 3 hats, and you plan to wear a shirt
and a hat today. How many different outfits can you choose? Since
you can wear each of 3 hats with each of the 5 shirts, the total number
of outfits is 3 x 5 = 15. In general when you see "and", you can
Complementing - Counting the Opposite - This minus That.
How many rolls of two dice do not give you doubles? There are 36
rolls you can get with two dice (see probability
review), and 6 of them are doubles (1-1, 2-2, 3-3, 4-4, 5-5,
6-6). Therefore 36-6 = 30 of them are not doubles. When you
count the "complement" of something, think "subtraction"
Counting wrong on purpose, with a purpose.
There are 80 kids in the middle school, and I want to choose two to
organize a party. How many different ways can I choose these
two? The first person I choose can be anyone of the 80 kids, and
the second person I choose can be anyone from the 79 that are
leftover. By the multiplying principle, the number of ways I can
put these two together is 80 x79 = 6320, because each one of the 80
kids can be joined with each one of the 79. However this is
wrong! Because for any pair of kids, say Joe and Rachel, I count
them once when Rachel is chosen first and Joe is chosen second, and one
again when Joe is chosen first and Rachel is chosen second.
So my actual total of 6320 is wrong, but I know just exactly how
wrong. It is twice as big as the real number of pairs. If I
divide 6320 in half I get the correct answer of 3160 pairs.
Here are a number of examples
to illustrate the application of these
1. At the kosher kiosk
at Hershey Park you can buy a hot dog, chicken nuggets, or grilled
chicken sandwich. Along with that you can have plain chips or BBQ
chips. To drink you can get water, coke, sprite, diet coke, or
apple juice. Assuming you order a main course, chips and a drink,
how many different meals can you buy at Hershey Park?
There are 3 main courses, 2 kinds of chips, and 5 drinks. Each
main course can be combined with each kind of chips, which then can be
combined with each kind of drink. The answer is then 3 x 2 x 5 =
30 different meals.
Harry's pizza shop let's you put up to two toppings on a regular
pizza. The toppings include: mushrooms, onions, peppers, and
garlic. They also have a whole wheat crust pizza which comes either
plain or with everything. How many different kinds of
pizza can you order?
Since there are different rules for the different cursts, let's do the
regular crust and the whole wheat crust separately and add the number
together. The whole wheat crust is easy - there are only two
kinds of pizzas: plain and everything. For the regular crust we
can have either 0, 1, or 2 toppings. Let's count each one
seperately and add them together. There is one way to have zero
toppings, 4 ways to have one topping, and ... Two toppings is
just a little harder. There are four toppings (Mushroom, Onion,
Peppers, Garlic), so we have four choices for the first topping, and
three choices for the second topping. There are 4 x 3 ways
to join these together, gicing 12 different kinds of pizza.
However this method is wrong because it counts every pair twice.
Here is the list: M-O, M-P, M-G O-M, O-P,
O-G P-M, P-O, P-G G-M, G-O, G-P
notice that every pair of toppings is counted twice once forward and
once backwards. Therefore the correct number of two topping
pizzas is half of this - just 6. Let's go back and finish the
solution: 2 whole wheat + 1 no-topping regular crust + 4
one-topping regular crust + 6 two-topping regular crust = 13
total different pizzas.
have ten socks in a drawer, half white and half black. If you
choose two socks at random from the drawer, what's the chance that you
have a pair of white socks or a pair of black socks? If
your gut instinct is still to say 50/50, then you need to re-read this
page and the previous one on probability!
The chances of picking two white socks or two black socks equals the
number of ways to pick two white socks + the number of ways to pick two
black socks, divided by the total number of ways to pick two
socks. Let's handle this in pieces. The total number of
ways to pick two socks from a collection of 10 is 10 x 9 divided by 2 =
45. (You have seen this idea twice before - when you chose 2
toppings from 4, and when you chose 2 kids from 80). The number
of ways to choose two white socks is 5 x 4 divided by 2 = 10, and the
number of ways to choose two black socks is the same 10.
Therefore the total chance to pick a pair of socks from this drawer
that match is (10 + 10)/45 = 20/45 = 4/9.
have 10 socks in a drawer, half white and half black. If you
choose two socks at random from the drawer, what's the chance you do not get a match? Here we can
just take away the 20 matches from the total, to get (45 - 20)/45 =
25/45 = 5/9.
5. If there are 100 people in town, half men and half
women. Twelve of the men have blue eyes, twelve of the woman have
blue eyes, and all the rest have brown eyes. If two blue eyed
people marry, their children are blue-eyed. If two brown-eyed
people marry, their children are brown-eyed. If a brown-eyed
person married a blue-eyed person, then there is a 75% chance that the
kid is brown-eyed, and a 25% chance that it is blue-eyed. If you
pick a man and a woman at random, what is the chance that their first
child will be blue-eyed?
Solution: There are 50 men and 50 women, and so there are 50 x 50
= 2500 total possible matches. Out of these matches, only some
will yield blue-eyed babies. The blue-eyed babies come from the
blue-blue marriages, or from brown-blue (or blue-brown)
marriages. Out of the 2500 total marriages, there are 12 x 12 =
144 blue-blue marriages, and all of these will yield blue-eyed
children. Out of the 2500 total marriages, there are 38 x 12
brown-blue marriages + 12 x 38 blue-brown marriages = 912
marriages. In each of these 912 marriages, there is a 25% chance
to have a blue-eyed baby. That means we expect about 228 of these
marriages to have a blue-eyed baby. Finally adding 144 + 228 we
get 372 marriages out of 2500 that are expected have blue-eyed
babies. The probability that the first child of a random marriage
is a blue-eyed baby is 372/5000 = 7.44%
6. "A Real life Problem". A dad is buying bowling balls for
his three sons. The balls are identical except for the color, and
there are five colors. The dad would like each kid to get a
different color, but of course two or more might want the same
color. Is it worth it for the dad to give a speech to the kids
about how not everyone might get their first choice on the theory that
it is likely to be a fight about the same color, or should he just let
them choose and hope that they pick three different colors. Well
this decision should depend on the chance that there will be no fight
about the colors. So assuming that each kid will pick a color at
random from the available five colors (choices may not be random but at
least we will get a ballpark on the probability), what is the
probability that we end up with three different colored balls?
Solution: This problem is a direct application of the
multiplication principle of counting. We must count how many ways
for the kids to each pick a color, and how many of those ways have
three different colors. Each child has five choices for color, so
the total number of ways for all three kids to pick colors is 5 x 5 x 5
= 125. Let's make sure you understand this. Call the colors
A - E. Then here is the beginning of the list of possible ways
for the kids to pick colors:
AAA AAB AAC AAD AAE
ABA ABB ABC ABD ABE
ACA ACB ACC ACD ACE
ADA ADB ADC ADD ADE
AEA AEB AEC AED AEE
That is 25 possibilities. The same exact list repeats four more
times with the first person choosing B instead of A, and then C instead
of A, and then D instead of A, and then E instead of A. That
makes 25 x 5 = 125 possible ways to choose colors.
Out of all these ways, how many have three different colors?
Rather than write them all out and count explicitly, there are 5
choices for the first color, and then only 4 choices for the
next, and then only three for the last, making 5 x 4 x 3 = 60. So
the chance the kids will live in peace with three different colors
is 60/125 = 12/25. This is just under 50%. That's like a
of a coin -- I don't think a preemptive speech is in order!
many ways can I choose a committee of three people from a group of ten?
every outfit I wear has one hat, one jacket and one pair of shoes, how
many outfits can I wear if all my clothes match and I have 3 hats, 10
pairs of shoes, and 4 jackets?
Banana Split has three scoops of ice cream. Each scoop can have
any topping; there are 4 flavors of ice cream; and there four different
toppings. How many different Banana Splits can you order?
many different outcomes can there be when I roll 3 dice?
5. If I
roll three dice, how many ways can I roll a sum of 8 or more?
Under Construction All Year
Email me: email@example.com