Math 362 - Lab #3 - Fall 2002

Introduction to Probability Theory

Lab 3: Elementary combinatorics


Equipment: a bag containing colored objects of similar shape.

  1. 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?



  2. 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?













  3. 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.





  4. Reading assignment: Sections 1.7 & 1.8

Back to Math 362