¤ The total number of possibilities can be determined without actually counting each one individually.

Combinatorics: the method of counting the possibilities
For example: a tree diagram

Tree Diagram

Example 1:
A radio station announces that they are giving away a prize package to the first caller. The package involves 1 movie, 1 gift certificate, and 1 car. The movie choices are: Sin City and Saw III. The possible gift certificates are to Hollister and Buffalo. The possible choices of cars are a Lexus and Ford. What are all the possible packages a winner can choose from?

Task: figuring out the number of possible combinations of prize packages

The results of the tree diagram can also be determined using the Fundamental or Multiplicative Counting Principle because drawing a tree diagram can be time consuming with large amounts of data.




Example 2:
For lunch David has to have to choose a sandwich, drink and dessert. The cafeteria sells BLT, Tuna, and Club sandwiches. For drinks they offer, orange juice, iced tea, apple juice and coke, and as for dessert, they sell brownies and cookies. How many different combinations of sandwich, drink and dessert can one person make?



As the diagram illustrates, there are many different combinations David can have for lunch, a total of 24 different combinations. The tree diagram allows us to see all the different combinations. Using the tree diagram approach can be a hassle sometimes once the amount of choices increase drastically. So a simpler way to calculate the amount of possible choice was found.


Fundamental or Multiplicative Counting Principle

• A SIMPLER METHOD

¤ If a task is made up of stages with separate choices in each stage, the total number of ways of doing the task is m x n x p..., where 'm' is the number of choices for the 1st stage, 'n' is the number of choices for the 2nd stage and so on.
The Fundamental Counting Principle is applied in the following example.

Example 3:
Telephone numbers in Canada used to be 7 digits and they did not include an area code.

(a) How many 7 digit phone numbers are possible?

• Task: writing down 7 numbers
• Number of stages: 7
• Write 7 blanks

___ ___ ___ ___ ___ ___ ___

*Remember: Numbers can be repeated; however the phone number can NOT begin with 0

9 10 10 10 10 10 10 = 9 x 10 x 10 x 10 x 10 x 10 x 10

= 9 000 000
Therefore, there are 9 000 000 possible phone numbers.

(b) How many possible phone numbers are there that do not have two of the same numbers next
to each other?

*Remember: the phone number can NOT begin with 0; however the other numbers in the phone number can include 0.

9 9 9 9 9 9 9 = 478 2969

Therefore, there are 478 2969 phone numbers that do not have two of the same numbers next to each other.

(c) How many phone numbers do not repeat the same number at all?

9 9 8 7 6 5 4 = 544 320

Therefore, there are 544 320 phone numbers that do not repeat the same number at all.

Additive Counting Principle

If one task can be performed m ways, but can also be performed n ways, and if the two tasks and mutually exclusive, meaning they cannot be performed at the same time, then there are m + n ways of doing the task.

(The Additive Counting Principle is applied in the following example.)

Example 4:
Jim is playing Monopoly with his friends. They are playing with one die. Jim, during his turn, either wants to roll a 1, or a number higher than 4. How many ways are there for Jim to roll either a 1, or a number higher than 4?

Task: rolling the die
Number of Stages: 1

How many ways can Jim roll a 1? 1 way (just the number 1)

In how many ways can Jim roll a number higher than 4? 2 ways (5 and 6)

Can both tasks be done at the same time? No (Jim can only roll once during his turn) Therefore, the tasks are mutually exclusive.

By adding the two possible ways, we can figure out the total number of ways for Jim to roll a 1 or a number higher than 4.

Jim can roll the number he wants in 3 ways.




First tree diagram provided by <http://www.gliffy.com/>
Second tree diagram by tofu-la