Calculate probabilities using combinatorics, such as combinations and permutations

The Multiplication Principle of Counting 

Assume that you are conducting an experiment where the outcomes consist of combining two separate actions or tasks. As such, assume that there are \(n\) possibilities for the first task and that for each of the \(n\) possibilities, there are \(r\) possible ways to perform the second task. Thus, the total number of outcomes for the experiment is given by:

$$\text{Possible outcomes for the experiment} = nr$$

Example: Multiplication Principle of Counting

A high school student has 10 pairs of socks, 6 pairs of pants, and 20 shirts. If we assume that the student will wear anything else, how many ways can the student get dressed?

Solution

The number of ways a student can get dressed is given by:

$$10\times 6\times 20 =1,200\  \text{ways}$$

Permutations

In probability, we may be interested in the possible arrangement of a set of objects in order. If we are interested in the order of the arrangement of the objects, we call this arrangement a permutation.

Formally, a permutation of \(n\) objects is defined as the ordered arrangements of those particular objects.

The permutation of \(n\) objects can be found by using the multiplication rule of counting. For instance, in a soccer match, we have 11 players. Assume that we want to arrange the players in order. In how many ways can we do this? Intuitively we have:

$$11\bullet 10\bullet 9 \bullet 8 \bullet 7 \bullet \cdots 2 \bullet 1 = 39,916,800\ \text{ways}$$

Thus, the number of the permutation of \(n\) objects is given by:

$$n!=n(n-1)(n-2)\cdots 1$$

\(n!\)  is read as “n factorial.” Note that \(0!=1\). For example,

 $$ 5! = 5 \bullet 4 \bullet 3 \bullet 2 \bullet 1 = 120 $$

Note that the value of the factorial grows larger as the number of the objects increases. For instance, \(100!\) is too large to be accommodated by a conventional calculator. As such, most of the permutations problems involve arranging \(r\) of the \(n\) objects in order. Before we go into the formulation, consider the following example:

Example: Permutations #1

A certain qualification examination panel has shortlisted 12 candidates. The top three candidates are awarded some amount of money. How many ways can the top three positions awarded to the candidates?

Solution

Note all 12 candidates are eligible for the top three positions. Thus, there are 12 possible ways for the  first position, 11 for the second position, and 10 for the third positions so that the total number of ways to assign the top three positions are:

$$12\bullet 11 \bullet 10 =1,320\ \text{ways}$$

Note that this can be written as:

$$12\bullet 11 \bullet 10 =\frac{12!}{9!}=\frac{12!}{(12-3)!}=1,320\ \text{ways}$$

The example above sets our mind to the following definition:

Permutation of n objects taken r at a time, is the ordered arrangement of \(r\) of \(n\) objects, where \(r\leq n\) and given by:

$$ { _{ n }{ P }_{ r } }= \frac{n!}{(n-r)!},\ r\leq n$$

Example: Permutation #2

How many ways are there to select and arrange 3 letters from the letters A, B, C, D and E?

Solution

This is a permutation because we do care what order the letters are in. ABC is different than BAC, etc.

We have 5 letters and we are choosing 3 so we are looking at:

$$ { _{ 5 }{ P }_{ 3 } }=\frac{ 5! }{ \left( 5-3 \right) ! }= \frac{ 5! } { 2! }=\frac{ \left( 5*4*3*2*1 \right) }{ \left( 2*1 \right)} =\frac{ 120 }{ 2 } =60 $$

Example: Permutation #3

In an insurance company, there are a total of 8 actuaries. A manager wishes to assign three actuaries to certain urgent duties A, B, and C in that order. In how many ways can the manager do this?

Solution

We have a total of 8 actuaries and we need to choose 3 out 8. Thus we have:

$${ _{ 8 }{ P }_{ 3 } }=\frac{ 8! }{ \left( 8-3 \right) ! }=336\ \text{ways}$$

Combinations

If we are NOT interested in the order of the arrangement of a set of objects, we call this arrangement a combination.

A combination of \(n\) objects taken \(r\) at a time is defined as unordered selection of \(r\) elements of the original \(n\) objects (\(r-element\) subset of the larger \(n\)). It is given by:

$$ { _{ n }{ C }_{ r }}= \frac { n! }{ r!  \left( n-r \right) ! } $$

Note that we can write:

$$ { _{ n }{ C }_{ r }}={n \choose r}$$

\({n \choose r}\) is usually called binomial coefficient since it comes in a typical binomial expansion.

Example: Combination #1

How many ways are there to select a team of 5 from a group of 20 employees?

Solution

This is a combination because the order of the employees selected does not matter.

$$ { _{ 50 }{ C }_{ 5 }= }\frac { 20! }{ \left( 20-5 \right) !\bullet 5! } =\frac{ 20! }{ \left( 15!\bullet 5! \right) }=\frac{ \left( 20\bullet 19\bullet 18\bullet 17\bullet 16 \right) }{ \left( 5\bullet 4\bullet 3\bullet 2\bullet 1 \right) }=15,504 $$

We can use combinations to calculate the probability of selecting certain arrangements of objects.

Example: Combination #2

What is the probability that we will select all hearts when selecting 5 cards from a standard 52 card deck?

Solution

The number of possible 5-card hands is 52 choose 5 or \({52!}/{(5! \bullet 47!)} = 2598960\).

The number of ways to choose 5 hearts is 13 choose 5 or \({13!}/{(5!*8!)} = 1287\)

So, the probability of selecting all hearts is:

$$ {1287}/{2598960} = .000495 \ or \ .0495\% $$

Multiplication, Permutation, and Combination

Note that some problems require you to combine knowledge from the multiplication, permutations, and combinations. Consider the following examples:

Example: Multiplication, Permutation, and Combination #1

A large insurance company has 20 male and 30 female actuaries. A welfare committee needs to be formed, which consists of 3 male and 5 female actuaries.

Calculate the number of ways in which the committee will be formed.

Solution

We need to choose 3 male actuaries from a group of 20 and 5 female actuaries from a group of 30 so that the number of ways of forming the committee is given by:

$${20 \choose 3}\times {30 \choose 5}=162,456,840\ \text{ways}$$

Example: Multiplication, Permutation, and Combination #2

In class, there are 50 students. Three students are running for the class representative, assistant class representative, and the class secretary, which the students elect. These officials are selected based on the number of votes, with the highest one being the class representative, followed by an assistant class representative, and lastly, the secretary. From the remaining 47 students, 5 students are selected to accompany the elected officials in every annual school meeting.

Calculate the number of ways the class can select its three officials and the accompanying group.

Solution

This problem requires us to rank the first three students (multiplication principle) and then choose five students from the remaining 47 students (combination):

$$3!\bullet {47 \choose 5}= 9,203,634\ \text{ways}$$

Partitions

From the word itself, partition involves breaking down a large group of objects into smaller groups. We have considered partition before through combinations (look at “Example: Multiplication Principle of Counting” above). Before we go into the formulation, let consider an example.

Example: Partition #1

An insurance company has 15 intern actuaries who are expected to be trained. The company will select 5 interns to be trained via a computer-based program, 4 through an online platform, and remaining through the traditional (face-to-face) method.

Calculate the number of ways in which the interns can be divided into the stated groups.

Solution

Using the partition analogy, we need to choose 5 interns from 15 for computer-based training and then choose 4 from the remaining 10 for the online training. Note once we have selected the group that will be trained online, the remaining 6 interns will take the traditional class.

Therefore, the number of ways to partition the group is given by:

$${15 \choose 5 }\bullet {10 \choose 4}=\frac{15!}{5!10!}\bullet \frac{10!}{4!6!}=\frac{15!}{4!5!6!}=630,630\ \text{ways}$$

Another example is when we are interested in how many arrangements can be made from a group of objects where some objects are repeating.

Formally, the number of \(n\) objects divided into \(r\) different groups of sizes \(n_1, n_2, \cdots n_r\)  is given by:

$$ {n \choose {n_1, n_2, \cdots n_r }}=\frac { n! }{ { n }_{ 1 }!\bullet { n }_{ 2 }!\bullet \cdots \bullet { n }_{ r }! } $$

Example: Partition #2

How many ways are there to arrange the letters A, A, B, B, C, D, and E?

Solution

 We have 7 letters of which 2 are repeating twice.

$$ =\frac { n! }{ { n }_{ 1 }!\bullet { n }_{ 2 }!\bullet \cdots { n }_{ r }! } =\frac { 7! }{ \left( 2!\bullet 2! \right) }=\frac{ \left( 7\bullet 6\bullet 5\bullet 4\bullet 3\bullet 2\bullet 1 \right) }{ \left( 2\bullet 1\bullet 2\bullet 1 \right) }=\frac { 5040 }{ 4 }=1260 $$

Example: Partition #3

An insurance company has 20 employees, where each employee is eligible to work in any department. The company divides the employees so that 7 go to marketing, 4 to underwriting, and the remainder to investments.

Calculate the number of ways in which the company can subdivide its employees.

Solution

The answer is given by:

$${20 \choose {7,4,9 }}=\frac{20!}{7!4!9!}=55,426,800\ \text{ways}$$

Learning Outcome

Topic 1.f: General Probability – Calculate probabilities using combinatorics, such as combinations and permutations.