Trees

By the end of this section, you should be able to:
- Organize outcomes in a sample space using tree diagrams.
- Compute the number of ordered arrangements of outcomes using permutations.
- Compute the number of (nonordered) groupings of outcomes using combinations.
- Explain how counting techniques relate to probability in everyday life.

To calculate the total number of possible outcomes in an experiment with multiple steps, we will utilize the Multiplication Rule of Counting.

Definition: The multiplication rule of counting specifies that if you have a series of events, the total number of possible outcomes is the product of the number of outcomes for each event.
Formula: If our events are denoted by $E1, E2, ext{ and } Em$, with possible outcomes $n1, n2, …, nm$, then:
n1 imes n2 imes ext{…} imes nm gives the total number of possible outcomes for the series of events $E1$ followed by $E2$, up through event $Em$.

Scenario: Suppose you own three shirts and four pairs of pants. The question is: how many different outfits can you create?
Solution: Each shirt has four pants choices, thus the total combinations are:
ext{Total Outfit Combinations} = 3 imes 4 = 12
This scenario can be formulated through the multiplication rule of counting.

Scenario: Jacqueline’s undergrad program requires her to take one course in psychology, one in physiology, and one in Spanish, with two sections of psychology, two of physiology, and three of Spanish offered.
Possible Outcomes: This can be modeled as an experiment consisting of three events where each course represents an event:
- Psychology: 2 Sections
- Physiology: 2 Sections
- Spanish: 3 Sections
Solution: Applying the multiplication rule,
ext{Total Class Schedules} = 2 imes 2 imes 3 = 12
This indicates that Jacqueline has 12 distinct class schedules to choose from.

Tree diagrams provide a way to visually organize and compute the probabilities of various outcomes in experiments involving multiple events.

Scenario: Imagine five discs in an urn (three red and two blue). If one disc is drawn and noted, then not replaced, followed by drawing another disc, we examine the possible outcomes.
Possible Outcomes: The tree diagram represents:
- First Draw: Red (R) or Blue (B)
- Second Draw: Based on the first draw's outcome, the probabilities shift:
- Drawing an R leads to possibilities of R or B in the second draw, while drawing a B will shift the probabilities as well.
Possible Outcomes Represented:
- RR (Red on 1st, Red on 2nd)
- RB (Red on 1st, Blue on 2nd)
- BR (Blue on 1st, Red on 2nd)
- BB (Blue on 1st, Blue on 2nd)

Dependent Events: The probability associated with the second disc depends on the first disc drawn which creates dependencies among the events.
By using the multiplication rule for these dependent events, we can compute the probabilities of each approach:
- For instance, the probability of drawing an R on both draws:
  P(RR) = P(R ext{ on 1st}) imes P(R ext{ on 2nd after R})
- The total probability should sum to 1, validating our outcomes.

Definition: A permutation is a selection of objects where order matters. Each unique arrangement is called a permutation.
Formula: For $n$ distinct objects, they can be arranged in n! ways. Examples include:
- For $3$ objects:
- Total ways = 3! = 3 imes 2 imes 1 = 6
To arrange $r$ objects from $n$ distinct objects, the formula is:
P(n, r) = rac{n!}{(n - r)!}

Scenario: Compute the number of possible ordered seating arrangements for eight people in five chairs.
Application: Using the formula where $n = 8$ and $r = 5$:
P(8, 5) = rac{8!}{(8 - 5)!} = rac{8!}{3!} . Evaluating this gives distinct seating arrangements.

Definition: A combination is similar to a permutation but does not concern the order in selections.
Formula for Combinations: The number of combinations of $n$ objects taken $r$ at a time is given by:
C(n, r) = rac{n!}{r!(n - r)!}

Scenario: Assigning to read $4$ books from a list of $10$.
The task is to find the number of combinations without regard to order since the sequence of reading doesn't change the outcome of the set chosen.
- Applying:
  C(10, 4) = rac{10!}{4!6!} = 210
This solution indicates that there are 210 ways to choose 4 books from 10.