Trees and Counting

Using Trees

We have seen that probability is defined by

                                    Number in E
        P(E)   =                                                           
                          Number in the Sample Space      

Although this formula appears simple, counting the number in each can prove to be a challenge.  Visual aids will help us immensely.  

 

Example

A native flowering plant has several varieties.  The color of the flower can be red, yellow, or white.  The stems can be long or short and the leaves can be thorny, smooth, or velvety.  Show all varieties.  

Solution

We use a tree diagram.  A tree diagram is a diagram that branches out and ends in leaves that correspond to the final variety.  The picture below shows this.

 

       

To read this tree diagram, we begin from start.  then move along the branches collecting words until we get to the end.  For example, 

  • Always taking the upper path leads to the selection of a red long thorny plant. 

  • Always taking the lower path leads to a blue short velvety plant.  We can count the total number of leaves (path endings) and get that there are 18 possible varieties.  

  • Counting the leaves that came from long stems tell us that there are 9 possible long stemmed varieties.

     

Example

A committee of three republican senators and four democratic senators is selected to investigate corporate securities fraud.  Out of this committee two members are to be selected at random for a subcommittee on the energy sector.  

  1. What is the probability that both members will be republican?
  2. What is the probability that both members will be democrat?
  3. What is the probability of one of each?

Solution

We write a tree diagram

       

In this tree diagram, D represents democrat and R represents republican.  The probabilities are given in the diagram.

To answer part A, we need to find

        P(first is R and second is R)

This corresponds to the bottom leaf.  As we travel to the bottom leaf, we pick up the two numbers

        P(R and R)  =  (3/7)(1/3)  =  1/7

To answer part B, we need to find 

        P(first is D and second is D)

This corresponds to the top leaf.  We have

        P(D and D)  =  (4/7)(1/2)  =  2/7

To answer the part C we add the two middle leaves

        P((D and R) or (R and D))  =  (4/7)(1/2) + (3/7)(2/3)  =  2/7 + 2/7  =  4/7

Permutations

Example

Suppose that 40 women try out for the newest play that has an all women cast of seven.  You are the director.  How many choices do you have?

 

Solution

The way to work this problem out is to consider the main role first.  You have 40 choices for the main role.  For the lead supporting actor there are 39 left to select from.  For the next role there are 38 to select from.  Now following this pattern and consider that there are seven in the cast gives a total number of choices as

        40 . 39 . 38 . 37 . 36 . 35 . 34

We could multiply these all out, however there is an easier way.  We can write

                                                            33 . 32 . 31 . ... . 2 . 1
       40 . 39 . 38 . 37 . 36 . 35 . 34                                                        
                                                            33 . 32 . 31 . ... . 2 . 1

                   40!
        =                       
               (40 - 7)!

This expression has a special notation.  We write

                          40!
        P40,7  =                 =  93,963,542,400
                      (40 - 7)!

We can see that there are plenty of choices.

In general we write

                          n!
        Pn,r  =                    
                     (n - r)!

  We call this a permutation.

Combinations

Example

How many 5 card poker hands are there?  

 

Solution

We can solve this in a similar way as the prior question.  We are selecting 5 cards out of 52 total.  Unfortunately this is not quite a permutation since, for example, the hand

        2H   3H   4H   5H   6H 

is the same as the hand 

        3H   5H   2H   6H   4H

where "H" means hearts.  That is the order at which the cards are dealt does not matter.  The number of ways of ordering 5 cards is 5! (five choices for the first card, four left for the second, three left for the third, two for the fourth, and one for the fifth).  We divide by this number to get our solution

                       52!
        =                               
                 (52 - 5)! 5!

We write this with the notation 

        C52,5  =  2,598,960

In general, we have 

                              n!
        Cn,k  =                            
                         (n - k)! k!

    and call this a combination.  

Example

The following was taken from the California state lottery web site:

"SuperLottoPlus is your chance to win millions of dollars! The jackpot ranges from $7 million to $50 million or more. The jackpot rolls over and grows whenever there is no winner. All you have to do is pick five numbers from 1 to 47 and one MEGA number from 1 to 27 and match them to the numbers drawn by the Lottery every Wednesday and Saturday."

What is the probability of winning the lottery?

 

Solution

There is only one element in the event space.  Your numbers.  For the sample space, first they pick 5 numbers from 47.  There are 

        C47,5  =  1,533939

ways of doing this.

Next they select a number from 1 to 27.  There are 27 ways of doing this.  We multiply to get 

        1,533939 x 27  =  41,416,353

So your chances are worse than one in forty-million.

Back to the Probability Home Page

Back to the Elementary Statistics (Math 201) Home Page

Back to the Math Department Home Page

e-mail Questions and Suggestions