Introduction to Counting Techniques
Welcome to the study of Counting (formally known as Combinatorics) in Discrete Mathematics! You might wonder: "Why do we need a whole chapter on counting when we learned how to count in primary school?"
In Further Mathematics, we often need to count possibilities in complex scenarios—such as calculating the number of secure passwords, organising network connections, or finding the number of valid routes in an algorithm—where listing every single outcome by hand would take thousands of years! This chapter provides the mathematical tools to count large sets of possibilities systematically, quickly, and accurately.
Did you know? Combinatorics is the foundational backbone of modern computer science, cryptography, and data encryption. Every time you log into a secure website, mathematical counting principles are working behind the scenes to keep hackers from guessing your credentials!
Key Takeaway: Counting in discrete mathematics is not about tallying items one by one; it is about finding structured patterns and formulas to determine total possibilities efficiently.
1. The Fundamental Principles of Counting
Before tackling complex formulas, all counting relies on two simple common-sense rules: the Multiplication Principle and the Addition Principle.
The Multiplication Principle (The "AND" Rule)
If a task consists of two sequential stages, where the first stage can be done in \(m\) ways and the second stage can be done in \(n\) ways, then the total number of ways to complete the entire task is:
\(\text{Total Ways} = m \times n\)
Real-world Analogy: Imagine choosing an outfit. If you have \(4\) shirts AND \(3\) pairs of trousers, you have \(4 \times 3 = 12\) different outfit combinations.
The Addition Principle (The "OR" Rule)
If an event can occur in one of two mutually exclusive (non-overlapping) ways, where the first option has \(m\) possibilities and the second option has \(n\) possibilities, then the total number of ways to choose one option is:
\(\text{Total Ways} = m + n\)
Real-world Analogy: If you are buying a hot drink and the café offers \(5\) types of coffee OR \(3\) types of tea, you have \(5 + 3 = 8\) total drink options to choose from.
Quick Memory Aid:
- AND means Multiply (\(\times\))
- OR means Add (\(+\))
2. Factorials and Permutations (When Order Matters)
What is a Factorial?
The factorial of a positive integer \(n\), written as \(n!\), is the product of all positive integers from \(n\) down to \(1\):
\(n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1\)
By definition, we also have the special case:
\(0! = 1\)
Permutations of Distinct Objects
A permutation is an arrangement of items in a specific order. Order matters!
For example, the race finish order First: Alice, Second: Bob is completely different from First: Bob, Second: Alice.
1. Arranging \(n\) distinct items in a line:
The number of ways to arrange all \(n\) items is simply \(n!\).
2. Arranging \(r\) items chosen from \(n\) distinct items:
When we choose and arrange only \(r\) items out of a total pool of \(n\) items, we use the permutation formula:
\(^n\text{P}_r = \frac{n!}{(n-r)!}\)
Example: In a running race of \(8\) sprinters, how many ways can the Gold, Silver, and Bronze medals be awarded?
Here \(n = 8\) and \(r = 3\):
\(^8\text{P}_3 = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336\text{ ways}\).
Permutations with Repeated (Identical) Items
If you have \(n\) items, but some of them are identical copies of each other, listing them normally would cause double-counting. To fix this, we divide by the factorial of each group of repeated items:
\(\text{Arrangements} = \frac{n!}{p! \times q! \times r! \dots}\)
where \(p, q, r, \dots\) are the frequencies of each repeated item.
Example: How many distinct arrangements can be made using all the letters in the word CHEESE?
- Total letters: \(n = 6\)
- Letter frequencies: \(\text{C: } 1\), \(\text{H: } 1\), \(\text{E: } 3\), \(\text{S: } 1\)
- Number of unique arrangements: \(\frac{6!}{3! \times 1! \times 1! \times 1!} = \frac{720}{6} = 120\).
3. Handling Restrictions in Arrangements
Don't worry if arrangement problems with conditions look intimidating. There are two standard methods you can always rely on:
Method 1: Items Must Be Together (The "Glue" or "Block" Method)
When specific items must stay together, treat them as a single combined block.
Step-by-step process:
1. "Glue" the restricted items together into one mega-item.
2. Count the total number of items (including the mega-item) and arrange them.
3. Multiply by the internal arrangements of the items inside the mega-item.
Example: In how many ways can \(3\) boys and \(2\) girls sit in a row if the \(2\) girls must sit together?
- Step 1: Group the \(2\) girls into \(1\) single unit: \((G_1 G_2)\).
- Step 2: We now have \(3\) boys + \(1\) girl-unit = \(4\) units to arrange. These can be arranged in \(4! = 24\) ways.
- Step 3: Inside the unit, the girls can swap places in \(2! = 2\) ways.
- Total arrangements = \(4! \times 2! = 24 \times 2 = 48\text{ ways}\).
Method 2: Items Must Be Separated (The "Slot" or "Gap" Method)
When certain items must never sit next to each other, place the unrestricted items first and insert the restricted items into the gaps between them.
Example: How many ways can \(4\) boys and \(3\) girls sit in a line such that no two girls are adjacent?
- Step 1: Arrange the \(4\) boys first in a row: \(4! = 24\) ways.
- Step 2: Identify the available "gaps" on either end and between the boys: \(\_ B_1 \_ B_2 \_ B_3 \_ B_4 \_\). There are \(5\) possible slots.
- Step 3: Place the \(3\) girls into these \(5\) distinct slots: \(^5\text{P}_3 = \frac{5!}{2!} = 60\) ways.
- Total arrangements = \(24 \times 60 = 1440\text{ ways}\).
Circular Permutations
When arranging \(n\) distinct objects in a circle (e.g., around a round dinner table), there is no designated "first" position. Rotating everyone by one seat does not create a new relative arrangement.
\(\text{Arrangements in a circle} = (n-1)!\)
If the circle can be flipped over (like beads on a necklace or keys on a keyring where clockwise and anti-clockwise are identical), divide by \(2\):
\(\text{Necklace arrangements} = \frac{(n-1)!}{2}\)
Key Takeaway: For linear arrangements, use \(n!\). For items glued together, treat them as one block. For items kept apart, place everyone else first and use the gaps!
4. Combinations (When Order Does NOT Matter)
A combination is a selection of items where the order does not matter. Choosing Alice and Bob for a committee is identical to choosing Bob and Alice.
The Combination Formula
The number of ways to choose \(r\) items from a pool of \(n\) distinct items is given by:
\(^n\text{C}_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}\)
Permutation vs Combination:
- Permutation = Position matters (e.g., race winners, passwords, queues).
- Combination = Choice only (e.g., lottery numbers, committees, hands of cards).
Symmetry Property of Combinations
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\).
Worked Example: Committee with Restrictions
A committee of \(5\) members is to be formed from a group of \(6\) teachers and \(8\) students. How many different committees can be formed if the committee must contain at least 3 teachers?
Solution:
"At least 3 teachers" means we could have: (3 teachers AND 2 students) OR (4 teachers AND 1 student) OR (5 teachers AND 0 students).
- Case 1 (3 teachers, 2 students): \(\binom{6}{3} \times \binom{8}{2} = 20 \times 28 = 560\)
- Case 2 (4 teachers, 1 student): \(\binom{6}{4} \times \binom{8}{1} = 15 \times 8 = 120\)
- Case 3 (5 teachers, 0 students): \(\binom{6}{5} \times \binom{8}{0} = 6 \times 1 = 6\)
Applying the Addition Principle across mutually exclusive cases:
\(\text{Total Committees} = 560 + 120 + 6 = 686\).
5. The Pigeonhole Principle
The Pigeonhole Principle (also called Dirichlet's Box Principle) sounds simple, but it is an exceptionally powerful proof tool in Discrete Mathematics.
Basic Form
If \(n\) items (pigeons) are put into \(k\) boxes (pigeonholes) and \(n > k\), then at least one box must contain more than one item.
Real-world Analogy: If you have \(13\) pairs of socks and only \(12\) drawers, at least one drawer must contain at least two pairs of socks.
Generalized Pigeonhole Principle
If \(n\) items are distributed into \(k\) boxes, then at least one box must contain at least:
\(\left\lceil \frac{n}{k} \right\rceil\text{ items}\)
where the notation \(\lceil x \rceil\) represents the ceiling function (rounding up to the nearest integer).
Example: What is the minimum number of students needed in a room to guarantee that at least \(4\) of them were born in the same month?
- Number of boxes (months), \(k = 12\).
- We want \(\left\lceil \frac{n}{12} \right\rceil = 4\).
- In the worst-case scenario, every month has \(3\) students without any month reaching \(4\): \(12 \times 3 = 36\) students.
- Adding just \(1\) more student guarantees a month with \(4\) birthdays.
- Therefore, minimum \(n = 36 + 1 = 37\) students.
6. The Principle of Inclusion-Exclusion (PIE)
When sets overlap, simply adding their individual sizes leads to double-counting. The Principle of Inclusion-Exclusion provides a systematic way to find the size of the union of overlapping sets.
For Two Sets, \(A\) and \(B\):
\(|A \cup B| = |A| + |B| - |A \cap B|\)
For Three Sets, \(A\), \(B\), and \(C\):
\(|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |B \cap C| + |A \cap C|) + |A \cap B \cap C|\)
Why do we add back the intersection of all three?
When we subtract the two-set overlaps, the central overlap (elements in all three sets) gets subtracted three times after being added three times, meaning it was completely removed! We must add it back once at the end.
Worked Example
Find how many integers between \(1\) and \(100\) (inclusive) are divisible by \(2\), \(3\), or \(5\).
Solution:
Let \(A\), \(B\), and \(C\) be the sets of integers up to \(100\) divisible by \(2\), \(3\), and \(5\) respectively.
- \(|A| = \lfloor \frac{100}{2} \rfloor = 50\)
- \(|B| = \lfloor \frac{100}{3} \rfloor = 33\)
- \(|C| = \lfloor \frac{100}{5} \rfloor = 20\)
- \(|A \cap B|\) (divisible by \(\text{lcm}(2,3) = 6\)): \(\lfloor \frac{100}{6} \rfloor = 16\)
- \(|A \cap C|\) (divisible by \(\text{lcm}(2,5) = 10\)): \(\lfloor \frac{100}{10} \rfloor = 10\)
- \(|B \cap C|\) (divisible by \(\text{lcm}(3,5) = 15\)): \(\lfloor \frac{100}{15} \rfloor = 6\)
- \(|A \cap B \cap C|\) (divisible by \(\text{lcm}(2,3,5) = 30\)): \(\lfloor \frac{100}{30} \rfloor = 3\)
Using the Inclusion-Exclusion formula:
\(|A \cup B \cup C| = (50 + 33 + 20) - (16 + 10 + 6) + 3\)
\(|A \cup B \cup C| = 103 - 32 + 3 = 74\text{ integers}\).
7. Common Pitfalls & Exam Checklist
Top Mistakes to Avoid:
- Mixing up \(^n\text{P}_r\) and \(^n\text{C}_r\): Always ask yourself: "Does the order in which I pick them create a brand new outcome?" If yes, use permutations. If no, use combinations.
- Forgetting to arrange inside the group: In the "glue" method, remember to multiply by the factorial of the grouped items inside their block.
- Ignoring identical items: When arranging words with duplicate letters, always divide by the factorials of the repeated letters.
- Forgetting the alternating signs in PIE: Remember the sign pattern: Add single sets, Subtract pairs, Add triplets, Subtract quadruplets...
Quick Reference Summary
- Fundamental Principle: AND \(\implies \times\), OR \(\implies +\)
- Permutations (Order Matters): \(^n\text{P}_r = \frac{n!}{(n-r)!}\)
- Repeated Items: \(\frac{n!}{p!q!r!}\)
- Circular Arrangements: \((n-1)!\)
- Combinations (Order Doesn't Matter): \(\binom{n}{r} = \frac{n!}{r!(n-r)!}\)
- Pigeonhole Principle: \(\lceil n/k \rceil\)
- Inclusion-Exclusion (2 Sets): \(|A \cup B| = |A| + |B| - |A \cap B|\)