Unit 4: Discrete and Decision Mathematics – Counting
Welcome to Counting! Counting might sound like something you learned in primary school, but in Further Mathematics, it means something much more powerful: calculating the exact number of possibilities or arrangements in complex situations without having to list them all by hand. Whether it's working out lock combinations, choosing sports teams, or arranging items in a line, systematic counting is a core part of Unit 4 (GFM41).
Don't worry if this seems tricky at first – once you understand the basic rules and how to spot the difference between arranging items (where order matters) and selecting items (where order doesn't matter), you'll fly through these exam questions!
---1. Fundamental Counting Principles
Every counting problem is built on two simple principles: the Multiplication Principle and the Addition Principle.
The Multiplication Principle (The "AND" Rule)
If an event has several successive stages, and stage 1 can happen in \(m\) ways and stage 2 can happen in \(n\) ways, the total number of combined ways for both stages to happen is:
\(\text{Total ways} = m \times n\)
This extends to any number of stages: \(n_1 \times n_2 \times n_3 \times \dots \times n_k\).
Example: A cafeteria lunch deal offers a choice of 3 sandwiches, 4 snacks, and 2 drinks. How many different meal combinations can you make?
\(\text{Total meal combinations} = 3 \times 4 \times 2 = 24\)
The Addition Principle (The "OR" Rule)
If you have mutually exclusive choices (meaning you can pick one option OR another, but not both at the same time), you add the possibilities.
\(\text{Total choices} = m + n\)
Example: A student can choose either 1 project from a list of 5 Science topics OR 1 project from a list of 4 History topics. How many choices are there?
\(\text{Total choices} = 5 + 4 = 9\)
Key Takeaway: When combining independent choices together (A AND B), multiply. When choosing between separate alternative options (A OR B), add.
---2. Factorial Notation
Factorials are a shorthand way of writing the product of descending positive integers. For any positive integer \(n\), \(n\) factorial (written as \(n!\)) is:
\(n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1\)
Examples:
\(1! = 1\)
\(3! = 3 \times 2 \times 1 = 6\)
\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
Important Special Case:
\(0! = 1\)
Did you know? While it might seem odd that \(0! = 1\), it makes our permutation and combination formulas work consistently without dividing by zero!
Key Takeaway: Factorials represent the number of ways to arrange \(n\) distinct objects in a straight line.
---3. Permutations (Order Matters!)
A permutation is an arrangement of items where the order matters. Think of finishing 1st, 2nd, and 3rd in a race – winning gold is very different from winning bronze!
A. Arranging all \(n\) distinct items in a line
The number of ways to arrange \(n\) different items in a row is simply:
\(\text{Ways} = n!\)
Example: In how many ways can 6 different books be placed side-by-side on a shelf?
\(\text{Ways} = 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\)
B. Arranging \(r\) items chosen from \(n\) distinct items (\(^n\text{P}_r\))
When selecting and arranging only \(r\) items out of a total pool of \(n\) distinct items, we use the formula:
\(^n\text{P}_r = \frac{n!}{(n - r)!}\)
Example: Eight runners compete in a 100m sprint. How many different ways can the 1st, 2nd, and 3rd place medals be awarded?
Here, \(n = 8\) and \(r = 3\):
\(^8\text{P}_3 = \frac{8!}{(8 - 3)!} = \frac{8!}{5!} = \frac{8 \times 7 \times 6 \times 5!}{5!} = 8 \times 7 \times 6 = 336\)
C. Arrangements with Identical Items (Repetition)
When arranging \(n\) total items where some items are identical, we divide by the factorial of each repeated group so we do not double-count duplicate arrangements:
\(\text{Distinct arrangements} = \frac{n!}{p!\,q!\,r!}\)
where \(p, q, r\) are the frequencies of the repeating items.
Example: How many distinct arrangements can be made using all the letters in the word SUCCESS?
Total letters \(n = 7\). Letters repeating: 3 S's (\(p = 3\)), 2 C's (\(q = 2\)), 1 U, 1 E.
\(\text{Arrangements} = \frac{7!}{3! \times 2!} = \frac{5040}{6 \times 2} = \frac{5040}{12} = 420\)
---4. Permutations with Constraints
In CCEA exams, you will often meet questions where items must be placed in specific ways. Here are the standard methods to solve them:
Method 1: Items Kept Together ("Glueing" Method)
When certain items must stay next to each other, follow these steps:
1. Treat the grouped items as a single "super item" (glue them together).
2. Calculate the number of arrangements of the new, smaller set of items.
3. Multiply by the internal arrangements of the glued items (\(k!\)).
Example: 4 boys and 3 girls sit in a row. How many arrangements are there if all 3 girls must sit together?
Step 1: Glue the 3 girls into 1 block. Now we have 4 boys + 1 block = 5 units to arrange.
Step 2: Arrange the 5 units: \(5! = 120\).
Step 3: Arrange the 3 girls inside their block: \(3! = 6\).
Total: \(120 \times 6 = 720\)
Method 2: Items Kept Separated ("Gaps" Method)
When certain items must NOT sit next to each other:
1. Arrange the unrestricted items first.
2. Identify the "gaps" created between and on the ends of these items.
3. Place the restricted items into these available gaps.
Example: 5 boys and 2 girls sit in a row. The 2 girls must not sit next to each other.
Step 1: Arrange the 5 boys: \(5! = 120\) ways.
Step 2: The 5 boys create 6 available gaps (one at each end and four in between):
\(_ \text{ B } _ \text{ B } _ \text{ B } _ \text{ B } _ \text{ B } _\)
Step 3: Choose 2 gaps for the 2 girls and arrange them: \(^6\text{P}_2 = \frac{6!}{(6-2)!} = 6 \times 5 = 30\).
Total: \(120 \times 30 = 3600\)
Method 3: Positional Restrictions
If specific positions (such as the ends or middle) have restrictions, fill the restricted slots first using the multiplication principle, then fill the remaining slots.
Example: How many 4-digit odd numbers can be formed using the digits 1, 2, 4, 5, 7, 8 without repetition?
Last digit constraint: To be odd, the last digit must be 1, 5, or 7 (3 choices).
Remaining digits: There are 5 digits left to fill the first 3 positions: \(^5\text{P}_3 = 5 \times 4 \times 3 = 60\).
Total: \(60 \times 3 = 180\)
5. Combinations (Order Does NOT Matter!)
A combination is a selection of items where the order does not matter. Choosing person A and person B for a committee is the exact same committee as choosing person B and person A.
A. Formula for Combinations (\(^n\text{C}_r\) or \(\binom{n}{r}\))
The number of ways to choose \(r\) items from a group of \(n\) distinct items is:
\(^n\text{C}_r = \binom{n}{r} = \frac{n!}{r!(n - r)!} = \frac{^n\text{P}_r}{r!}\)
Example: A teacher needs to pick a team of 4 students from a class of 10. How many different teams can be formed?
\(\binom{10}{4} = \frac{10!}{4!(10 - 4)!} = \frac{10!}{4! \times 6!} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210\)
B. Symmetry Property
Choosing \(r\) items to include is mathematically identical to choosing \((n - r)\) items to leave behind:
\(\binom{n}{r} = \binom{n}{n - r}\)
Example: \(\binom{10}{8} = \binom{10}{2} = \frac{10 \times 9}{2 \times 1} = 45\)
---6. Combinations with Selections and Restrictions
A. Multi-Group Selections
When selecting team members from separate categories (e.g. men and women, adults and children), multiply the combinations for each category together.
Example: A committee of 3 teachers and 2 students is chosen from 8 teachers and 12 students. How many ways can this committee be formed?
\(\text{Teacher selections} = \binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56\)
\(\text{Student selections} = \binom{12}{2} = \frac{12 \times 11}{2 \times 1} = 66\)
\(\text{Total committees} = 56 \times 66 = 3696\)
B. "At Least" / "At Most" Conditions
You can solve these problems using one of two methods:
Method A: List all valid mutually exclusive cases and add them up.
Example: A committee of 4 is selected from 5 men and 6 women. How many committees contain at least 3 women?
The valid cases are:
Case 1: Exactly 3 women and 1 man \(\implies \binom{6}{3} \times \binom{5}{1} = 20 \times 5 = 100\)
Case 2: Exactly 4 women and 0 men \(\implies \binom{6}{4} \times \binom{5}{0} = 15 \times 1 = 15\)
\(\text{Total} = 100 + 15 = 115\)
Method B: Complementary Counting (Total − Unwanted)
Sometimes it is faster to subtract the unwanted cases from the total number of unrestricted selections:
\(\text{Valid selections} = \text{Total selections} - \text{Unwanted selections}\)
---7. Permutation vs. Combination: Quick Decision Guide
Ask yourself this crucial question: Does the order matter?
Permutation (\(^n\text{P}_r\)):
Order matters! Key words: arrange, line up, order, race positions (1st, 2nd, 3rd), distinct roles (President, Secretary).
Combination (\(^n\text{C}_r\)):
Order does not matter! Key words: choose, select, pick, committee, group, team.
8. Common Pitfalls & Examiner Tips
1. Mixing up \(^n\text{P}_r\) and \(^n\text{C}_r\): Electing named roles (Chair, Vice-Chair) is a permutation because roles are distinct. Picking 2 general representatives is a combination because they hold equal status.
2. Forgetting internal arrangements: When using the glueing method for grouped items, always remember to multiply by \(k!\) for the items inside the group.
3. Miscounting gaps: If you arrange \(k\) items in a line, there are always \(k + 1\) available gaps for the separated items.
4. Double-counting: When dealing with "at least one" conditions, do not pick one item first and then choose the rest freely from the remaining pool – this causes severe double-counting. Always break into distinct cases or use complementary counting.