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.   What is the probability that both members will be republican? What is the probability that both members will be democrat? 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 Elementary Statistics (Math 201) Home Page