The Fundamental Principle of Counting: Quick Revision

A brief note on The Fundamental Principle of Counting. Read it before a test. Try each question at the end before you open its answer.

The multiplication principle

• An event in $m$ ways, then another in $n$ ways: $m \times n$ ways in all. It extends to any number of stages.
• A tree diagram shows why. Every branch splits into the same number of branches.
• With repetition, each place keeps all its choices: $k$ places with $n$ choices give $n^k$.
• Without repetition, each place has one choice fewer: $n \times (n - 1) \times (n - 2) \times \dots$
• A number cannot start with $0$.

The addition principle

• A task in $m$ ways OR in $n$ other ways: $m + n$ ways, if no way is in both.
• Stages one after another: multiply. Separate cases: add.
• Split a hard count into cases that cannot overlap, count each, then add.
• Fill the place that has a rule first, such as an even or odd last digit.

Factorials

• $n! = 1 \times 2 \times \dots \times n$, and $0! = 1$.
• $n! = n \times (n - 1)!$, so each factorial comes from the one before.
• Cancel before multiplying: $\dfrac{n!}{(n - 2)!} = n(n - 1)$.
• A product of $k$ numbers counting down from $n$ is $\dfrac{n!}{(n - k)!}$.
• $(2n)! \neq 2 \times n!$, and $(a + b)! \neq a! + b!$.

A worked example

How many $4$-digit numbers with four different digits are greater than $6000$?

1. The first digit. It must be $6$, $7$, $8$ or $9$: $4$ ways.
2. The other places. Nine digits are left for the second place, then $8$ and $7$.
3. Multiply. $4 \times 9 \times 8 \times 7 = 2016$ numbers.

Practice with new numbers

A program to try

The program checks the three rules of this note by listing: a product of choices, a sum of separate cases, and the factorial rule.

Mistakes to avoid

• Adding stages. Choices one after another multiply.
• Keeping every choice without repetition. Each place loses one choice.
• Overlapping cases. Add only cases with nothing in common.
• $0! = 0$. It is $1$.
• Cancelling inside a factorial. $\dfrac{8!}{4!}$ is $8 \times 7 \times 6 \times 5$, not $2!$.

Check yourself

1. A password is one letter from A to Z followed by $2$ digits, which may repeat. How many passwords are there?

2. Dev chooses either one of $6$ films or one of $4$ plays. How many choices does he have?

3. How many $3$-digit numbers with different digits end in $0$?

4. Find $\dfrac{14!}{12!}$.

5. Why is $0! = 1$?