Counting principles

The text of this page is plagiarized from the Cambridge University Press book Mathematics Higher Level for the IB Diploma. The text here should be deleted.

Learning objectives

To be able to break down complicated questions into parts that are easier to count, and then combine them together,
To be able to count the number of ways to arrange a set of objects,
To be able to use the algebraic properties of a useful new tool called the factorial function,
To know how many ways one can choose objects from a group, and
To know various strategies for applying these tools to harder problems.

Introduction

Counting is one of the first things one learns in mathematics and at first seems very simple. If one was asked to count how many people there are in a school, this would not be a feat too tricky. If one were asked how many chess matches would need to be played if everyone were to play everyone else, this would be a little more complicated. If one were asked how many different football teams could be chosen, one might find that the number becomes too large to count coming up with some clever tricks. This chapter aims to help develop strategies for counting in such difficult situations.

The product principle and the addition principle

Menu

Mains

Pizza
Hamburger
Paella

Desserts

Ice-cream
Fruit salad

Counting very small groups is easy. So, one needs to break down more complicated problems into counting small groups. But how does one combine these together to come up with an answer to the overall problem? The answer lies in using the product principle and the addition principle, which can be illustrated using the following menu.

Anna would like to order a main course and a dessert. She can choose one of three main courses and one of two deserts. How many different choices could she make? Bob would like to order either a main course or a dessert. He can choose one of the three main courses or one of the two desserts; how many different orders can he make?

We can use the notation $n(A)$ to represent the number of ways of making a choice about $A$ .

The product principle allows one to select one option from $A$ and one option from $B$ , then one multiplies the individual possibilities together.

Product principle (AND rule) The number of ways in which both choice $A$ and choice $B$ can be made is the product of the number of options for $A$ and the number of options for $B$ :

$n(A{\text{ AND }}B)=n(A)\times n(B)$

The addition principle produces a result of individual possibilities if one were to select only one option from $A$ or one option from $B$ , then the result is simply adding the possibilities together.

The addition principle has one essential restriction. One can only use if if there is no overlap between the choices for $A$ and the choices for $B$ . For example, one cannot apply the addition principle to counting the number of ways of getting an odd number or a prime number on a die. If there is no overlap between the choices for $A$ and for $B$ , the two events are mutually exclusive.

Addition principle (OR rule) The number of ways in which either choice $A$ or choice $B$ can be made is the sum of the number of options for $A$ and the number of options for $B$ .

If $A$ and $B$ are mutually exclusive then:

$n(A{\text{ OR }}B)=n(A)+n(B)$

The hardest part of applying either the addition or product principle is breaking the problem down and deciding which principle to use. One must oneself to make sure that all cases have been checked to make sure they are mutually exclusive. It is often useful to rewrite equations to emphasise what is required, 'AND' or 'OR'.

The number of ways of selecting something $r$ times from $n$ objects is $n^{r}$ .

Counting arrangements

The word 'ARTS' and the word 'STAR' both contain the same letters, but are arranged in a different order. They are both arrangements (also known as permutations) of the letters R, A, T, and S. One can count the number of different permutations.

There are four possibilities for the first letter, then for each choice of the first letter there are three options for the second letter (because one of the letters has already been used). This leaves two options for the third letter and then the final letter is fixed. Using the 'AND rule' the number of possible permutations is $4\times 3\times 2\times 1=24$ .

The number of permutations of $n$ different objects is equal to the product of all positive integers less than or equal to $n$ This 'expression is abbreviated to $n!$ (pronounced 'n factorial').

Permutation A way of arranging a set of objects in a particular order. The number of ways of arranging $n$ objects is $n!$ :

$n!=n(n-1)(n-2)...\times 2\times 1$

Algebra of factorials

To solve more complicated counting problems one often needs to simplify expressions involving factorials. This is done by using the formula for factorials,

$n!=n(n-1)(n-2)...\times 2\times 1$

Then proceeding to look for common factors of the terms. It is important to understand the link between one factorial and the next:

$(n+1)!=(n+1)\times n!$

Being able to simplify expressions involving $n!$ is useful because $n!$ becomes very large very quickly. Often factorials cannot be evaluated even using a calculator. For example, a standard scientific calculator can only calculate up to $69!=1.71\times 10^{98}$ (to 3 significant figures).

Counting selections

Suppose that three pupils are able to be selected from a class of 11 to attend a meeting with the Head Teacher. How many different groups of three can be chosen?

In this example one needs to choose three pupils out of 11, but they are not to be arranged in any specified order. The order is not important; the selection of, say, Aspasia, Phryne, and then Rahab is the same as the selection of Phryne, Rahab, and then Phryne. This sort of selection is called a combination. In general, the formula for the number of ways of choosing $r$ objects out of $n$ is given the symbol ${n \choose r}$ or $^{n}C_{r}$ (pronounced 'n C r' or 'n choose r').

Combination A way of choosing a set of objects where the order does not matter. The number of ways of choosing $r$ objects out of $n$ is:

${n \choose r}={\frac {n!}{r!(n-r)!}}$

Exclusion principle

The exclusion principle is a way of counting what one is interested in by first counting what one is not interested in. This is often needed for counting where a certain property is prohibited (not allowed).

Exclusion principle Counting the number of outcomes that satisfy a given condition by first counting everything which does not satisfy the condition and then subtracting this from the total number of outcomes.

Imagine that a five-digit code is formed using each of the digits 1−5 exactly once. If one wanted to count how many such codes do not end in '25' one could work out all' of the possible options that do not end in '25'. This method works, but it is long and complicated. An easier way is to use the exclusion principle.

Counting ordered selections

Sometimes one has the requirement to choose a number of objects from a bigger group but the order in which they are chosen is important. For example, finding the possibilities for the first three finishers in a race or forming numbers from a fixed group of digits. The strategy for dealing with these situations is first to choose from the larger group and then permute the chosen objects.

Suppose that the whole set has a size $n$ and one is selecting and ordering a subset of size $r$ . The number of ways of doing this is given the symbol $^{n}P_{r}$ , and is described as 'the number of permutations of $r$ objects out of $n$ '. One can use the formula ${n \choose r}$ to deduce a formula for $^{n}P_{r}$ : there are ${n \choose r}$ ways of choosing the objects in the subject, and these can be arranged in $r!$ ways. Therefore,

$^{n}P_{r}={n \choose r}\times r!$

or, similarly:

$^{n}P_{r}={\frac {n!}{(n-r)!}}$

This can be written, using factorial algebra, to:

$^{n}P_{r}=n(n-1)(n-2)\ldots (n-r+1)$

Written in this form, one can see that the formula for $^{n}P_{r}$ , is an application of the 'AND rule.' For example, suppose that there are five people in a race and one wants to count the number of possibilities for the first three positions. One can reason t hat if there are five options for the winner then, for each winner, there are four options for the second place and three options for the third place. This gives $5\times 4\times 3=^{5}P_{3}$ .

Keeping objects together or separated

How many letter arrangements of the world 'SQUARE' have the Q and U next to each other? How many hove the vowels all separated? When a problem has constraints like this one needs some clever tricks to deal with them.

The first type of problem that shall be observed is where objects are forced to stay together. The trick is to imagine the letter in the word SQUARE as being on tiles. If the Q and U need to be together, one is essentially dealing with five tiles, con containing QU:

S	QU	A	R	E

One must also remember that the condition is satisfied if Q and U are in the other order:

S	UQ	A	R	E

Another sort of constraint is where objects have to be kept apart. This is not the opposite of objects being kept together unless one is separating only two objects. For example, the opposite of three objects staying together includes having two of them together and the third one apart. So when dealing with 'keeping objects apart' one needs to focus on the gaps that the critical objects can fit into.

Consider the question of how many permutations of the word SQUARE has where none of the vowels are together. One must first permute all of the consonants. One such permutation is

*	S	*	Q	*	R	*

Where * are the possible gaps where one can place the vowels. Only only has three vowels and so only need to choose three of the gaps, and then decide in what order to insert the vowels.