10.1 Fundamental counting principle and combinations

The fundamental counting principle

The use of lists, tables and tree diagrams is only feasible for events with a few outcomes. When the number of outcomes grows, it is not practical to list the different possibilities and the fundamental counting principle is used.

The fundamental counting principle describes how to determine the total number of outcomes of a series of events.

Suppose that two experiments take place. The first experiment has $n_1$ possible outcomes, and the second has $n_2$ possible outcomes. Therefore, the first experiment, followed by the second experiment, will have a total of $n_1\times n_2$ possible outcomes. This idea can be generalised to $m$ experiments as the total number of outcomes for $m$ experiments is:

$\prod$ is the multiplication equivalent of $\sum$ .

Note: the order in which the experiments are done does not affect the total number of possible outcomes.

Combinations

The fundamental counting principle describes how to calculate the total number of outcomes when multiple independent events are performed together.

A more complex problem is determining how many combinations there are of selecting a group of objects from a set. Mathematically, a combination is defined as an un-ordered collection of unique elements, or more formally, a subset of a set. For example, suppose you have fifty-two playing cards, and select five cards. The five cards would form a combination and would be a subset of the set of 52 cards.

In a set, the order of the elements in the set does not matter. These are represented usually with curly braces. For example $\{2,4,6\}$ is a subset of the set $\{1,2,3,4,5,6\}$ . Since the order of the elements does not matter, only the specific elements are of interest. Therefore,

and $\{1,1,1\}$ is the same as $\left\{1\right\}$ because in a set the elements don't usually appear more than once.

So in summary we can say the following: Given $S$ , the set of all possible unique elements, a combination is a subset of the elements of $S$ . The order of the elements in a combination is not important (two lists with the same elements in different orders are considered to be the same combination). Also, the elements cannot be repeated in a combination (every element appears once).

Counting combinations

Calculating the number of ways that certain patterns can be formed is the beginning of combinatorics , the study of combinations. Let $S$ be a set with $n$ objects. Combinations of $r$ objects from this set $S$ are subsets of $S$ having $r$ elements each (where the order of listing the elements does not distinguish two subsets).

Combination without repetition

When the order does not matter, but each object can be chosen only once, the number of combinations is:

where $n$ is the number of objects from which you can choose and $r$ is the number to be chosen.

For example, if you have 10 numbers and wish to choose 5 you would have 10!/(5!(10 - 5)!) = 252 ways to choose.

For example how many possible 5 card hands are there in a deck of cards with 52 cards?

52! / (5!(52-5)!) = $2598960$ combinations

Combination with repetition

When the order does not matter and an object can be chosen more than once, then the number of combinations is:

where $n$ is the number of objects from which you can choose and $r$ is the number to be chosen.

For example, if you have ten types of donuts to choose from and you want three donuts there are (10 + 3 - 1)! / 3!(10 - 1)! = 220 ways to choose.

Note that in this video permutations are mentioned, you will cover permutations in the next section.

Combinatorics and probability

Combinatorics is quite useful in the computation of probabilities of events, as it can be used to determine exactly how many outcomes are possible in a given experiment.