Sunday, July 14, 2013

# The tree diagram concept to solve counting problems. GRE Math

2:26 AM
Counting problems in GRE may ask you to determine how many different ways you can select or arrange objects such as alphabets in a word, toppings on a pizza, friends within a group, etc. Let’s take a simple example:
A pizza shop, Healthy Pizza R’us offers 3 different sizes of pizza: Small, Medium and Large. Let’s also assume (for simplicity sake!) the shop only allows one selection among 4 different healthy toppings: Onions, Ham, Olive and Pepper and Olives. How many different ways can you order a pizza? If you care to do the counting i.e. Small size with Ham topping, Small Size with Pepper toppings, and so on there are 12 different ways you can order the pizza.
An easy way to visualize and count different outcomes is a tree diagram. The tree diagram that you see below is a simple visual aid in making the two decisions: the size and the topping. The number of leaves is the product of the number of first level options times the number of second level options - in this case, 3 × 4 = 12. We realize this is not really a tree since the stem is above the leaves. However consider it as an inverted tree i.e. leaves down and stem up!

### The tree diagram concept to solve counting problems

This brings us the simple Two-Step Counting principle!
For any operation that can be performed in two steps, if there are  $\usepackage{color} \definecolor{Myblue}{rgb}{0.27,0.38,0.5} \color{Myblue} m$ distinct ways of performing step 1 and  $\usepackage{color} \definecolor{Myblue}{rgb}{0.27,0.38,0.5} \color{Myblue} n$ distinct ways of performing step 2, then the total number of possible ways the operation can be performed is the product $\usepackage{color} \definecolor{Myblue}{rgb}{0.27,0.38,0.5} \color{Myblue} m \times n$

We only talked about a two-step process. However the same principle applies for 3 or more steps.
Example:
Andy has 2 different trousers: Black and Gray and three different shirts: White, Yellow and Cream. If he has 4 possible choices for socks: Red, Orange, Pink and Tan, in how many different ways can he dress himself on any given day?
A) 9
B) 12
C) 18
D) 24
E) 30
Solution:

Now we agree that working with this awful wardrobe will be a challenging experience for anyone. However trust us when we tell you that mathematically this is fairly easy problem.
This is a simple application of multiplication principle. There are 2 ways of choosing a trouser, 3 ways of choosing a shirt and 4 ways of choosing the socks. Therefore there are a total of 2 × 3 × 4 = 24 ways that Andy can dress using this wardrobe.