Counting Principles and Factorials
Theory
The multiplication principle counts choices made one after another, and factorial notation, \(n! = n \times (n - 1) \times \cdots \times 1\), counts the ways to arrange \(n\) objects in a row. This Year 10A maths page covers arrangements with and without repetition, identical objects, objects kept together, subsets of a set, and probabilities found by counting, with and without replacement.
The multiplication principle: if one choice can be made in \(m\) ways and, after it, a second choice in \(n\) ways, the two choices together can be made in \(m \times n\) ways. It extends to any number of stages, and a tree diagram shows why.
Factorial notation: \(n! = n \times (n - 1) \times \cdots \times 2 \times 1\), read "\(n\) factorial". For example \(4! = 4 \times 3 \times 2 \times 1 = 24\). By definition \(0! = 1\).
An arrangement is an ordering of objects in a row. \(n\) different objects can be arranged in \(n!\) ways: \(n\) choices for the first place, \(n - 1\) for the second, and so on. If some objects are identical, swapping them gives nothing new, so there are fewer arrangements.
A subset of a set is any selection of its elements, including the empty set \(\{\,\}\) and the whole set. Each element is either in or out, so a set with \(n\) elements has \(2^n\) subsets. For example \(\{a, b, c\}\) has \(2^3 = 8\): \(\{\,\}, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\).
Choosing with replacement means an item can be chosen again (repetition allowed); without replacement means it cannot. When outcomes are equally likely, a probability is the number of favourable outcomes divided by the total number of outcomes, both found by counting.
| Counting | Number of ways |
|---|---|
| \(r\) choices, each from \(n\), repetition allowed | \(n^r\) |
| \(n\) different objects in a row | \(n!\) |
| \(r\) of \(n\) different objects in order | \(\dfrac{n!}{(n - r)!} = n(n - 1)\cdots(n - r + 1)\) |
| \(n\) objects in a row, \(a\) of one kind alike, \(b\) of another alike | \(\dfrac{n!}{a!\,b!}\) |
| subsets of a set with \(n\) elements | \(2^n\) |
How to count
- Ask two questions: does order matter, and is repetition allowed?
- Draw a box for each stage or place and write the number of choices in it. Fill restricted places first (for example "must start with a vowel").
- Multiply the numbers in the boxes.
- Divide if some objects are identical (by \(a!\) for each group of \(a\) alike), or if order does not matter (by \(r!\)).
Useful tricks
- Must be together: glue them into one block. Arrange the block with the other objects, then multiply by the number of ways to arrange the objects inside the block.
- Must not be together: total arrangements minus the arrangements where they are together.
- Fixed pattern (such as alternating): fill the places for each group separately and multiply.
- "At least one": total minus the number with none. A set of \(n\) elements has \(2^n - 1\) non-empty subsets.
- Subsets containing a particular element: that element is fixed as "in", and each of the other \(n - 1\) is in or out: \(2^{n-1}\).
- Probability: count the favourable outcomes and the total, then simplify the fraction. For draws one after another you can also multiply probabilities along a tree diagram.
(i) How many codes are possible if letters and digits may repeat?
(ii) How many are possible if no letter and no digit may repeat?
(iii) A code is made at random, with repeats allowed. Find the probability that it has no repeated letter or digit.
(i) Four boxes: \(26\) choices for each letter and \(10\) for each digit.
| \(26 \times 26 \times 10 \times 10\) | \(=\) | \(\mathbf{67\,600}\) |
(ii) Without repeats, each choice has one fewer option than the one before it of the same kind.
| \(26 \times 25 \times 10 \times 9\) | \(=\) | \(\mathbf{58\,500}\) |
(iii) Every code in (i) is equally likely.
| \(P(\text{no repeats})\) | \(=\) | \(\dfrac{58\,500}{67\,600} = \mathbf{\dfrac{45}{52}}\) |
(ii) In how many ways can \(6\) different books be arranged in a row?
(iii) A club of \(8\) students chooses a captain, a vice-captain and a secretary. In how many ways can this be done? Show that the answer equals \(\dfrac{8!}{5!}\).
| \(\text{(i)}\ \ \dfrac{9!}{7!}\) | \(=\) | \(\dfrac{9 \times 8 \times 7!}{7!}\) |
| \(\) | \(=\) | \(9 \times 8 = \mathbf{72}\) |
| \(\text{(ii)}\ \ 6!\) | \(=\) | \(6 \times 5 \times 4 \times 3 \times 2 \times 1\) |
| \(\) | \(=\) | \(\mathbf{720}\) |
| \(\text{(iii)}\ \ 8 \times 7 \times 6\) | \(=\) | \(\mathbf{336}\) |
(iii) The order matters, because the three jobs are different: \(8\) choices for captain, then \(7\), then \(6\).
| \(\dfrac{8!}{5!}\) | \(=\) | \(\dfrac{8 \times 7 \times 6 \times 5!}{5!}\) |
| \(\) | \(=\) | \(8 \times 7 \times 6 = 336 \ \checkmark\) |
(i) How many different arrangements are there?
(ii) In how many of them are the three Ps together?
(iii) An arrangement is chosen at random. Find the probability that the three Ps are together.
(i) There are \(6\) letters: three Ps, two Es and one R. Divide by the orders of the identical letters.
| \(\dfrac{6!}{3!\,2!}\) | \(=\) | \(\dfrac{720}{6 \times 2} = \mathbf{60}\) |
(ii) Glue the Ps into one block PPP. Now arrange \(4\) items: PPP, E, E, R, with two Es alike. The Ps inside the block are identical, so they add no extra orders.
| \(\dfrac{4!}{2!}\) | \(=\) | \(\dfrac{24}{2} = \mathbf{12}\) |
| \(\text{(iii)}\ \ P(\text{Ps together})\) | \(=\) | \(\dfrac{12}{60} = \mathbf{\dfrac{1}{5}}\) |
(i) How many ordered draws are possible without replacement? With replacement?
(ii) Find the probability that both counters are red, without replacement and with replacement.
| \(\text{(i) without}\) | \(:\) | \(10 \times 9 = \mathbf{90}\) |
| \(\text{with}\) | \(:\) | \(10 \times 10 = \mathbf{100}\) |
(ii) Count the ordered draws with two red counters the same way.
| \(\text{without}\) | \(:\) | \(\dfrac{4 \times 3}{90} = \dfrac{12}{90} = \mathbf{\dfrac{2}{15}}\) |
| \(\text{with}\) | \(:\) | \(\dfrac{4 \times 4}{100} = \dfrac{16}{100} = \mathbf{\dfrac{4}{25}}\) |
Check with a tree diagram: without replacement, \(\dfrac{4}{10} \times \dfrac{3}{9} = \dfrac{12}{90} = \dfrac{2}{15}\) \(\checkmark\). The chance is smaller without replacement, because one red counter has already gone.
Common pitfalls
Frequently asked questions
What does n! mean?
n factorial is the product of all the whole numbers from n down to 1. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. It counts the ways to arrange n different objects in a row.
Why is 0! equal to 1?
There is exactly one way to arrange nothing. Defining 0! = 1 also keeps the rule n! = n × (n − 1)! true when n = 1, and makes formulas such as n! divided by (n − r)! work when r = n.
How many subsets does a set with n elements have?
2 to the power n. Each element is either in a subset or not, giving 2 choices per element. This count includes the empty set and the whole set.
When do I divide in a counting problem?
Divide when the multiplication counts the same result more than once: when some objects are identical, or when the order of a group does not matter. Divide by the number of orders of each group.
What is the difference between with and without replacement?
With replacement, an item goes back before the next choice, so the number of options stays the same and repeats are possible. Without replacement, the number of options drops by one at each step.