Statistics for Decision Makers - 05.03 - Probability - Combinatorics

From Training Material
Jump to navigation Jump to search
title
05.03 - Probability - Combinatorics
author
Bernard Szlachta (NobleProg Ltd) bs@nobleprog.co.uk

Ways of arranging things 。

  1. Possible Orders
  2. Multiplication Rule (Cartesian Product, Cross Product)
  3. Permutations
  4. Combinations

Possible Orders。

ClipCapIt-140526-161904.PNG


Suppose you had a plate with three pieces of candy on it: one green, one red and one yellow.

  • You are going to pick up these three pieces one at a time.
  • In how many different orders can you pick up the pieces?

Possible Orders Example 。

The table below lists all the possible orders.

ClipCapIt-140526-160856.PNG


  • There are two orders in which red is first: red, yellow, green and red, green, yellow
  • Similarly, there are two orders in which yellow is first and two orders in which green is first
  • This makes six possible orders in which the pieces can be picked up

Possible Orders Formula 。

The formula for the number of orders is shown below.

Number of orders = n!
where n is the number of pieces to be picked up. The symbol "!" stands for factorial. 
In a spreadsheet
=FACT(3)

Some examples are:

3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
5! = 120

Multiplication Rule (Cartesian Product, Cross Product)。

Imagine a small restaurant whose menu has 3 soups, 2 main courses, and 3 desserts. How many possible meals are there?

  • The answer is calculated by multiplying the numbers to get 3 x 2 x 3 = 18
  • You can think of it as first there is a choice among 3 soups
  • Then, for each of these choices there is a choice among 2 main course resulting in 3 x 2 = 6 possibilities
  • Then, for each of these 6 possibilities there are 3 possible desserts yielding 6 x 3 = 18 total possibilities

ClipCapIt-140528-153329.PNG ClipCapIt-140602-233204.PNG

Permutations。

ClipCapIt-140526-161827.PNG

Suppose that there were four pieces of candy (green, red, brown, and yellow).

  • You are only going to pick up exactly two pieces.
  • How many ways are there of picking up two pieces?

Permutations Example。

The table below lists all the possibilities.

ClipCapIt-140526-162115.PNG
  • The first choice can be any of the four colours.
  • For each of these 4 first choices there are 3 second choices.
  • Therefore there are 4 x 3 = 12 possibilities.

Permutations Formula。

The number of permutations of four things taken two at a time.

  • In other words, it is the number of ways r things can be selected from a group of n things
  • The general formula is:

ClipCapIt-140526-162532.PNG

where nPr is the number of permutations of n things taken r at a time.

In a spreadsheet
=PERMUT(4,2)

ClipCapIt-140526-162615.PNG

It is important to note that order counts in permutations.

  • That is, choosing red and then yellow is counted separately from choosing yellow and then red
  • Therefore permutations refer to the number of ways of choosing rather than the number of possible outcomes
  • When order of choice is not considered, the formula for combinations is used

Combinations。

Now suppose that you were not concerned with the way the pieces of candy were chosen but only in the final choices.

  • In other words, how many different combinations of two pieces could you end up with?
  • In counting combinations, choosing red and then yellow is the same as choosing yellow and then red because in both cases you end up with one red piece and one yellow piece.
  • Unlike for permutations, order does not count.

Combinations Example。

  • The table below is based on the table above but is modified so that repeated combinations are given an "x" instead of a number
  • For example, "yellow then red" has an "x" because the combination of red and yellow was already included as choice number 1
  • There are six combinations of the four colours

ClipCapIt-140526-162814.PNG

Combinations Formula。

The formula for the number of combinations is shown below where nCr is the number of combinations for n things taken r at a time.

ClipCapIt-140526-162840.PNG

For our example,

ClipCapIt-140526-162855.PNG

which is consistent with the table above.

Combinations Example。

ClipCapIt-140527-234159.PNG

Suppose there were six kinds of toppings that one could order for a pizza. How many combinations of exactly 3 toppings could be ordered?

  • Here n = 6 since there are 6 toppings and r = 3 since we are taking 3 at a time.
  • The formula is then:

ClipCapIt-140526-163410.PNG

In a spreadsheet
=COMBIN(6,3)

Quiz。

Please find the Quiz here

Quiz

1 Order counts in

permutations
combinations

Answer >>

permutations

Order counts in permutations. For combinations, only the final result matters, not how you get to it. Order does not count for combinations.


2 A pizza restaurant has 5 types of toppings. You are going to choose 2 toppings. How many possible sets of 2 toppings are there for you to choose from?

Answer >>

10

This is asking for combinations with 5 items (types of toppings) taken 2 at a time. 5!/(3! x 2!) equals 120/12 equals 10.



3 You flip a coin and then roll a die. What is the probability of obtaining a head on the coin and a 4 on the die?

Answer >>

.0833

Since these are independent events you apply the multiplication rule: (.5 x .1667 equals .0833)


4 You are going to select first and second place prizes out of 5 entries. How many possible outcomes are there?

Answer >>

20

This is asking for permutations with 5 items (entries) taken 2 at a time (first place and second place). 5!/(3!) equals 120/6 equals 20.


5 You select a special team of 3 out of your 100 employees. This is an example of:

permutations
combinations

6 Out of 100 products, you want to create a package of 2. This is an example of:

permutations
combinations