Previous:  Probability Basics

In the previous article we saw that the basic technique for evaluating the probability of some event A was to compute the number of outcomes that belong to A, and then to divide this by the total number of outcomes in the sample space S.  This of course requires us to do some counting, firstly of the number of outcomes in A, and then the number of outcomes in S.

For simple problems, for example tossing a coin or rolling a die, this counting can be done simply by enumerating the various possibilities.  For more complex examples, this is not feasible and so we need to apply mathematical techniques for counting outcomes.  We will consider five such techniques in this section:

1.  The multiplication method;

2.  Sampling with replacement;

3.  Permutations – sampling without replacement;

4.  Combinations – order not important;

5.  Splitting elements into groups.

These are the basic tools for counting outcomes, and will be considered in turn.

The Multiplication Method

The multiplication method can be applied to an experiment that takes place in multiple steps, each of the steps being independent from each other.  Suppose that such an experiment takes place in k stages.  Suppose that the first stage gives rise to N₁ outcomes, the second stage gives rise to N₂ outcomes, and so on and so forth.

How many total outcomes are there?  The answer is just

The reason is that each of the total outcomes consists of one component from each of the k stages of the experiment.  For a given total outcome, the component from the first stage can be chosen in N₁ ways, and the second component can be chosen in N₂ ways.  Thus, there are a total of N₁N₂ ways in which the first and second components of the total outcomes can be formed.  Continuing in this way for the other components of the total outcome leads to the result above.

Example:  How large is the sample space when 10 dice are rolled?  The individual rolls of each die can be taken as independent.  Each die can give rise to any one of six numbers.  Thus the size of the sample space is 6 × 6 × 6 × 6 × 6 × 6 × 6 × 6 × 6 × 6 = 6¹⁰ = 60,466,176.

Example:  Neglecting leap years, in a group of k people, how many possible sequences of birthdays are there, assuming that the birthdays are equally likely to fall on any day of the year?  Assuming that the birthdays of the members of the group are independent, then any one person could have any one of 365 birthdays.  Thus the total number of sequences of birthdays is 365^k.

Sampling with Replacement

The term “sampling with replacement” refers to a very well-known example that is used to illustrate the concept.  Consider an experiment in which a box contains n balls, each of which has a different colour.  Now, a ball is removed at random from the box, its colour is noted, and the ball is placed back in the box (hence the term “with replacement”).  The experiment is repeated a total of k times – a ball is selected, the colour noted, and the ball is put back into the box.

The question is, what is the size of the sample space S for the complete experiment of k selections and replacements?  The first ball can be selected in any one of n ways.  The second, third and all other balls that are selected in the experiment can also be selected in any one of n ways, because the balls are replaced after selection and therefore there are always n balls to choose from.  Thus, for k selections with replacement, the size of the sample space is just

Example:  How many ways can 8 balls be selected, with replacement, from a box containing 10 balls?  From the formula above, the total number of ways is 10⁸.  Thus, the sample space for this experiment (selection of 8 balls from 10 with replacement) is 10⁸ or 100,000,000.

Permutations – Sampling Without Replacement

Now let us consider the same experiment as in the previous section, except that this time we will not replace the balls once we have pulled them out of the box.  Let us assume that the number of selections k is less than the number of balls in the box n.  Once again, the first ball can be selected in any one of n ways.  But now the second ball can only be selected in any of (n – 1) ways, because we did not replace the first ball.  Continuing in this way, the k^th ball can only be selected in any of (n – k + 1) ways.

Thus, for k selections without replacement, the size of the sample space is given by

where the exclamation mark denotes a factorial, and we conventionally take 0! = 1.

To put this more generally, suppose that we are picking k items from a total of n.  The total number of selections, with order important, is called a permutation and is given by the result stated above.

Example:  How many ways can 10 cards be selected from a deck of 52 cards?  The first card can be selected in 52 ways, the second card in 51 ways, etc.  Thus we can use the formula above, and the total number of selections is 52!/(52-10)! = 52!/42!

Combinations – Order not Important

In the previous section, we were concerned with choosing objects without replacement, and – just as important – by implication we were concerned with the ordering of the objects that we selected.  If we are concerned with sampling distinct objects, for example cards from a pack of cards, then this is the appropriate way to proceed.

But let us consider a different example, namely choosing a subset of boys from a larger group.  Let us suppose that we want to select 6 boys from a group of 12.  If we label the 12 boys with the letters A through to L, then the two selections

            ABCDEF

            BCDAEF

are different, if we are interested in the order in which we select the boys, for example to fill different posts in a club or school.  Now suppose that ANY 6 boys will do.  In this case, the two selections above are identical, because we are only interested in selecting any 6 boys and hence we are not interested in the order in which we select them.

The question is, how many ways can we choose any 6 boys?  If order is important, then the answer is that there are a total of 12!/6! selections of the type listed above.  If we consider any of these selections, for example ABCDEF, then there are 6! ways in which the items of this selection can be rearranged and still leave an identical selection.  Thus, if order is not important, then there are 12!/(6!6!) different possible selections

If order is not important, then any of the permutations belongs to a “group” of k! other permutations that can be considered identical.  The number of selections with order not important is called a combination and is given by

Example:  A class in a school consists of 20 boys and 25 girls.  How many ways can 10 boys and 15 girls be selected from the class?  In this case, order is not important, we are only interested in picking any 10 boys and any 15 girls.  The boys can be picked in 20!/(10!10!) ways, and the girls in 25!/(10!15!) ways.  Thus the total number of ways of picking 10 boys and 15 girls is 20!/(10!10!) × 25!/(10!15!) ways.

Splitting Elements into Groups

Finally, we will consider the problem of counting how many ways a fixed number of objects can be split into a fixed number of groups, when the numbers of items to go into each group are prescribed.

Let us consider n objects to be split into k groups, such that we place n₁ objects into the first group, n₂ objects into the second group, and so on and so forth.  Order is not important.

Now, the first n₁ objects for the first group can be chosen in C(n,n₁) ways.  This leaves n – n₁ objects from which the n₂ objects for the second group can be chosen.  This can be achieved in C(n – n₁,n₂) ways.  We can proceed in this way until all k groups have been filled.  The total number of ways that all k groups can be filled in this way is

Using the expression in the previous subsection for the combination C and cancelling out factorials leads to

Example:  Let us split a class of 20 children into 3 groups, such that the first group has 6 members, the second group has 12 members and the third group has 2 members.  How many ways can this be done?  Using the expression above, the answer is 20!/(6!12!2!).

Next:  Bayes Theorem