Math 362 - Lab #3 - Fall 2002
Introduction
to Probability Theory
Lab 3: Elementary combinatorics
Equipment: a bag containing colored objects of similar shape.
- The multiplication rule
- As in the previous lab, the objects in the bag are only of two possible colors,
which we will call Color A and Color B. There are 8 objects of Color
A and 4 objects of Color B in the bag.
- Consider an experiment which consists in drawing 5 objects with replacement and
recording the color of each of them. An outcome for this experiment is a 5-tuplet,
whose entries are the colors of each object, in the order in which the objects were
drawn. Perform the experiment once, and record the outcome below.
- We want to count how many possible outcomes there are. Draw a tree which
shows that there are 2 possible colors for the first object drawn; that regardless of
the first outcome, there are 2 possible colors for the second object drawn; that regardless of
the first two outcomes, there are 2 possible colors for the third object drawn; etc ...
- Use the tree to figure out how many outcomes are in the sample space of this
experiment. Are all outcomes equally likely? Why or why not?
- More generally, if an experiment consists in drawing n objects and if there
are two possible choices for each drawing, what is the number of possible outcomes of this
experiment?
- Permutations
- In this section, we will find out how many ways there are of ordering 4 objects.
- Start with 4 objects of different colors. List below all of the possible ordered
arrangements of these 4 objects. Each of them is known as a permutation. How
many permutations of 4 objects are there?
- More generally, assume that we have n different objects. Find a formula for the number
of permutations of these n objects. Explain your reasoning.
- Let us go back to the 4 objects, but now suppose that two of them have the same color. List below
all of the different permutations one can have. Note that we assume that the two objects
which have the same color cannot be distinguished. How many permutations did you find? How does this number
compare to the case where the 4 objects have different colors?
- Repeat the above in the case where 3 of the 4 objects have the same color.
- Assume that you have n objects, m of which are identical. How many permutations are
there of these n objects? Explain your reasoning.
- Finally, assume that you have n different objects and that you select k of them
without replacement. How many possible outcomes (note that the order in which the objects are listed matters)
are there for such an experiment? This number is known as the number of permutations of n objects,
taken k at a time. How does this formula relate to your answer to the previous question? Explain.
- As an application, take 5 objects of different colors and choose 2 of them without replacement. List
the different possible outcomes below (the order matters). How many outcomes are there? Does this number
agree with the formula found above?
- Combinations
- In the last example above, the order in which the objects were drawn mattered. For instance,
(Blue, Red) was counted as different from (Red, Blue).
If the order does not matter, each of these pairs corresponds to having drawn "one red and one blue"
objects and are therefore identical.
- Go back to your list of 5 objects taken 2 at a time, and cross out those outcomes which are redundant
when the order does not matter. How many possible groups of 2 are you left with? Each of these groups
is called a combination. How does the number of combinations relate to the number of possible
outcomes when the order matters, i.e. to the number of permutations? Can you see why?
- More generally, what is the number of possible non-ordered groups or combinations of n objects,
taken k at a time? Explain.
- Reading assignment: Sections 1.7 & 1.8
Back to Math 362