Faculty of Mathematics Centre for Education in

Waterloo, Ontario N2L 3G1 Mathematics and Computing

Grade 7/8 Math Circles

November 8 & 9, 2016
Combinatorial Counting

Learning How to Count (In a New Way!)

Right now, you are probably thinking, “Counting? I know how to count! What kind of a
lesson is this? What is this madness???” How about this: in today’s lesson, we will learn
about different ways of counting things, how to count the number of different possibilities
and outcomes of actions or events. Counting actually falls under a branch of mathematics
called combinatorics. By the end of this lesson, you will be the Master Yoda of counting
sharing your knowledge and wisdom with your own young padawans.

Warm Up
Make a Smoothie
You’re making yourself a smoothie after a long day at school. In the kitchen, you have
3 different types of milk: organic, lactose-free, or 2% and 3 different fruits: strawberries,
bananas, or mangoes. How many different smoothies can you make?

1
Product Rule (Fundamental Counting Principle)

Product Rule (or the Fundamental Counting Principle)

If there are m ways of doing one action and n ways of doing another action, then there
are m × n ways of doing both actions.

Example It’s getting chilly outside and you have to choose which hat and scarf you want
to wear. You have a plain red hat and a striped blue hat. And you have a plain blue scarf,
striped green scarf, and a spotted red scarf. How many different hat and scarf combinations
can you wear?

Sum Rule

Sum Rule
If there are m ways of doing one action and n ways of doing another action, then there
are m + n ways of doing one action or the other action.
(Note: Both actions cannot be done together)

Example You are at the movie theatre to watch Doctor Strange with your friends. You
have enough money to buy popcorn or nachos. There are three sizes of popcorn: small,
medium, and large. And there are three kinds of nachos: cheese, chili cheese, or no cheese.
How many movie snack options do you have?

2
Factorials
Try this! Suppose you are arranging three balls in a line: one red, one blue, and one yellow
ball. How many different arrangements are there?

Let n be a whole number. The factorial of a whole number, denoted as n!, is the product
of all whole numbers less than or equal to n.

n! =

We read this as “n-factorial”.

Example 1 Calculate the following:

(a) 3! (b) 4! (c) 5!

It may be helpful to note that...

n! = n × (n − 1)!

We can see this in true in the previous examples.

Example 2 You and 5 other friends are watching the Toronto Maple Leafs game. In how
many different ways can you and your friends sit in your seats?

3
A few notes about factorials...

• 0! is a special case. We can say that 0! = 1

• We can only find the factorials of positive integers (or positive whole numbers)
(i.e. π!, 2.81!, and (-3)! are not possible to find)

Multiplying and Dividing Factorials

Yes, it is possible to multiply and divide factorials! Take a look at the following examples.

Multiplying Factorials

Calculate 3! × 2!

Nothing really new here with multiplying.

Dividing Factorials
7!
Dividing factorials is a little more interesting. Calculate the following:
4!

12!
Example Calculate
13!

4
Permutations (Order Does Matter!)
Consider the following problem:

You’re making a two-layer cake and have four flavours of cake to choose from: vanilla,
chocolate, strawberry, and red velvet.

Question: How many different two-layer cakes can you make?

(Suppose each layer is different and you cannot repeat a flavour.)

Answer this by making a tree diagram.

Answer:

Is there an easier way to solve this instead of always making a tree? YES!

Let’s try to answer this using what we have learned so far.

5
Our answer, written using factorials, is called a permutation. Permutations are used when
we are counting objects where ORDER DOES MATTER and there is no repetition. Since
we are counting how many different layered cakes we can make, the order of the flavour of
the cake layers does matter and we are not repeating flavours.

Permutations
If there are n objects to choose from and we choose only k out of the n objects (where
order does matter), then

n Pk =

We read n Pk as “n permute k”.

We divide n! by (n − k)! because out of the n objects we have, we are only using k of them
so we do not count the remaining (n − k) objects.

Example Emmet is building a LEGOTM tower made of 3 blocks only. There are 12 blocks
to choose from. How many different ways can Emmet build his tower?

6
The Birthday Problem
This is a classic counting problem and you may see many variations of this problem if you
continue to study statistics and probability.

Challenge! There are 35 students in our class. What is the probability that at least two
students in class share the same birthday? (Assume there are 365 days in a year.)

7
Combinations (Order Does Not Matter!)
Let’s use our cake example again. You’re making a two-layer cake and you have four flavours:
vanilla, chocolate, strawberry, and red velvet.

Question: How many different two-layer cakes can you make?

(Suppose the order of the layers does not matter.)

A table of all possible two-layer cakes has been listed below for you...

V, C C, V S, V R, V
V, S C, S S, C R, C
V, R C, R S, R R, S

Since the order of the cake layers does not matter, we need to remove some answers from the
table. For example, V, C is considered to be the same as C, V. We are currently double
counting the possible cakes we can make.
Circle the possible two-layer cakes and cross out all the double counted cakes.

Answer:

To solve this question without all the double counting stuff, we can use something called
combinations. We can use combinations to count objects where ORDER DOES NOT
MATTER and there is no repetition.

Combinations
If there are n objects to choose from and we choose k of the n objects (where order does
not matter), then
 
n
n Ck = =
k
 
n
We read n Ck or as “n choose k”.
k

We divide n! by k! because there are k! ways to order the selected k out of n objects and
order does not matter. If we do not divide by k!, we are counting each combination k times
and we will not have the correct solution. We also divide n! by (n − k)! because again, we
do not want to count the remaining (n − k) objects that were not selected.

8
Alright, now using combinations this time, how many different two-layer cakes can you make
given that the order of the layers does not matter?

Example 1 There are 16 students on your school’s student committee and there are 3
available executive positions. How many different ways can 3 students be elected from the
student committee?

9
Example 2 Fourteen biologists applied to be part of an expedition team to study and
explore the Great Barrier Reef in Australia. This team will consist of 5 selected biologists.
Exactly 6 of them are trained in marine biology. If the expedition requires at least 3 of them
to be trained, how many different expedition teams can be selected?

10
Pascal’s Triangle
In the 16th century, Pascal’s Triangle was named after the French mathematician Blaise
Pascal because of his work but interestingly enough, Pascal was definitely not the first to
arrange these numbers into a triangle. It was worked on by Jia Xian in the 11th century in
China, then it was popularized in the 13th century by Chinese mathematician, Yang Hui and
became known as Yang Hui’s Triangle. Yet again, even before Yang Hui, it was discussed
and known in the 11th as the Khayyam Triangle in Iran and was named after the Persian
mathematician Omar Khayyam.

Isn’t cool how people are able to study and discover mathematics from different parts of the
world?

For this lesson, we will call it Pascal’s Triangle. The triangle is built as follows:

row 0 −−−−−−−−−−−−−−→ 1
row 1 −−−−−−−−−−→ 1 1
row 2 −−−−−−−−→ 1 2 1
row 3 −−−−−−→ 1 3 3 1
row 4 −−−→ 1 4 6 4 1
row 5 → 1 5 10 10 5 1

Each number in Pascal’s Triangle can be written as a combination as seen below.

 
0
  0  
1 1
  0   1  
2 2 2
  0   1   2  
3 3 3 3
  0   1   2   3  
4 4 4 4 4
  0   1   2   3   4  
5 5 5 5 5 5
0 1 2 3 4 5
 
n
In general, the k-th number in the n-th row can be written as .
k

11
Problem Set

1. A combo meal at a restaurant includes a drink, food item, and fresh fruit. The restau-
rant serves two drinks (juice and pop), three food items (sandwich, wrap, and salad),
and three fresh fruits (an apple, orange and grapes). How many different combos can
a customer order?

2. D.W. goes to the library to borrow some books. There are 3 picture books, 6 fictional
books, and 4 non-fictional books she is interested in reading. How many books can she
read?

3. For each of the following scenarios, state whether order matters or not:

(a) The number of ways four distinct sets of plates at the dinner table.
(b) Mr. Elgoog is asked to draw three cards from a deck of cards. In how many ways
can he select three cards?
(c) A math student is given a list of 8 problems and is asked to solve any 5 of the
problems. How many different selections can the student make?
(d) Selecting a combination on a combination lock.

4. You and a group of friends are at Canada’s Wonderland planning your route around
the park. You are all interested in 6 rides, 4 games, and 3 food vendors.

(a) How many different routes consisting of one ride, one game and one food vendor
could you take?
(b) How different routes consisting of three rides, two games, and one food vendor
could you take?

5. Draw Pascal’s Triangle up until the 8th row.

6. Find the missing numbers in this row of Pascal’s Triangle.

(Hint: Count how many numbers there are in the row.)

1 78 186 1287 1716 1287 186 78 1

12
 7. Evaluate the following:

(a) 7 P3
 
11
(b)
4
(c) 15 C2

6 C4
(d)
12 C3

14 P5
(e)
14 C7

8. How many different ways can you arrange the letters of the word TRIANGLE?

9. A vehicle licence plate number consists of 4 letters followed by 3 digits.

(a) How many different licence plates are possible?

(b) How many different licence plates are possible if we cannot repeat any letters and
digits?

10. Tommy, Chuckie, Phil, Lil, and Angelica go to the movies to watch Fantastic Beasts
and Where to Find Them.

(a) How many different seating arrangements of the five friends are possible?
(b) Tommy and Chuckie are bros and want to sit next to each other. How many
different seating arrangements are possible?

11. * How many numbers between 1000 and 9999 have only even digits?

12. * How many three-digit numbers begin with 4, 6, or 7 AND end with 0 or 1?
 
n
13. ** Solve for n in the following: = 55
2
14. ** How many different ways can you order the letters of the word MATHEMATICS?
     
11 11 12
15. *** Show that + = is true by using the combinations formula.
2 3 3
16. *** The Birthday Problem (continued) There are n students in a classroom.
What is the probability that at least two students in class share the same birthday?

13