Welcome to Mathematical Preliminaries!
Welcome to the world of Discrete Mathematics! Unlike the math you’ve done in Calculus, which deals with "smooth" things like curves, Discrete Math focuses on "separated" or "countable" objects. Think of it as the difference between a ramp (continuous) and a staircase (discrete).
In this chapter, we are building your "toolbox." These preliminaries are the fundamental rules for counting and organizing objects. They might seem simple at first, but they are the secret engine behind computer science, scheduling, and even winning at board games!
1. The Four Types of Problems
In Discrete Mathematics, almost every challenge you face will fall into one (or more) of these four categories. Understanding which one you are dealing with is half the battle!
A. Existence: Can it be done? This asks if a solution actually exists. Example: Can we color a map using only four colors so that no two touching countries have the same color?
B. Construction: How do we do it? If a solution exists, this is the step-by-step recipe to build it. Example: Drawing the actual map colors mentioned above.
C. Enumeration: How many ways are there? This is the heart of "counting." Example: How many different ways can you color that map?
D. Optimisation: What is the "best" way? Usually, this means finding the shortest, fastest, or cheapest solution. Example: What is the fastest route for a delivery driver to visit ten houses?
Key Takeaway:
Before you start a problem, ask yourself: "Am I trying to find IF it's possible (Existence), HOW to do it (Construction), HOW MANY ways there are (Enumeration), or the BEST way (Optimisation)?"
2. The Language of Sets and Partitions
A Set is just a collection of objects (like a set of numbers or a set of students). To master this chapter, you need to understand Partitions.
A Partition of a set means breaking it into smaller "piles" (subsets) such that:
1. Every item from the original set is in a pile.
2. No item is in more than one pile (no overlaps).
3. No pile is empty.
Analogy: If you have a deck of cards and you group them by suit (Hearts, Diamonds, Spades, Clubs), you have created a partition of the deck. Every card has a home, and no card is both a Heart and a Spade.
Counting Partitions: Sometimes you’ll be asked to count how many ways you can partition a set. For example, if you have 3 different books and want to put them into 2 non-empty piles, you could have (Book A) and (Book B, C), or (Book B) and (Book A, C), or (Book C) and (Book A, B). That's 3 ways!
3. The Pigeonhole Principle
This is one of the most famous (and fun!) rules in math. Don't worry if it sounds too simple—its power comes from how you apply it.
The Rule: If you have \(n+1\) pigeons and only \(n\) pigeonholes, at least one pigeonhole must contain more than one pigeon.
Real-World Example: If there are 13 people in a room, at least two of them must share the same birth month. Why? Because there are only 12 months (the "holes") and 13 people (the "pigeons").
Quick Review: To use this in a problem, identify what are your "pigeons" (the things you are distributing) and what are your "holes" (the categories they go into).
4. The Multiplicative Principle
This is the "Golden Rule" of counting.
If you have 'a' ways of doing one thing and 'b' ways of doing another, then there are \(a \times b\) ways of doing both.
Example: If a cafe offers 3 types of sandwiches and 4 types of drinks, how many lunch combos can you make?
Answer: \(3 \times 4 = 12\) combos.
Arranging Objects: If you have \(n\) distinct (different) objects and you want to arrange them all in a line, the number of ways is \(n!\) (n factorial).
\(n! = n \times (n-1) \times (n-2) \times ... \times 1\).
Example: Arranging 5 different books on a shelf? \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\) ways.
5. Permutations vs. Combinations
This is where many students get stuck, but here is a simple trick to remember the difference:
Permutations (\(_nP_r\)): Order MATTERS. Think "P" for "Position."
Use this when you are picking people for specific jobs (like Gold, Silver, and Bronze medals).
Formula: \(_nP_r = \frac{n!}{(n-r)!}\)
Combinations (\(_nC_r\)): Order DOES NOT matter. Think "C" for "Committee."
Use this when you are just picking a group where everyone is equal (like picking 3 friends to go to the cinema).
Formula: \(_nC_r = \frac{n!}{r!(n-r)!}\)
Did you know?
A "combination lock" should actually be called a "permutation lock" because the order of the numbers matters!
6. Arrangements with Constraints
Sometimes the world isn't simple, and we have restrictions. Here are two common scenarios:
A. Repetition (Identical Objects)
If you are arranging letters in a word where some letters are the same, you must divide by the duplicates.
Example: How many ways to arrange the letters in "EGG"?
Total letters = 3. Duplicate 'G's = 2.
Answer: \(\frac{3!}{2!} = \frac{6}{2} = 3\) ways. (EGG, GEG, GGE).
B. Restrictions ("Not Together")
If two people, Alice and Bob, refuse to stand next to each other in a line of 5 people, use the Gap Method:
1. Arrange the other 3 people first (\(3!\)).
2. Look at the gaps around them: _ P1 _ P2 _ P3 _ (There are 4 gaps).
3. Pick 2 gaps for Alice and Bob to sit in (\(_4P_2\)).
4. Multiply them: \(3! \times \text{}_4P_2\).
7. The Inclusion-Exclusion Principle
When counting things in groups, we often accidentally count people twice if they belong to two groups. We use this principle to fix that.
For Two Sets (A and B):
\(n(A \cup B) = n(A) + n(B) - n(A \cap B)\)
Translation: (Total in A or B) = (Count A) + (Count B) - (Count those in both).
For Three Sets:
The pattern is Add, Subtract, Add:
1. Add the individual sets.
2. Subtract the pairs that overlap.
3. Add the triple overlap (the center of the Venn diagram) back in.
Common Mistake:
Forgetting to subtract the intersection! If 10 people like Apple and 10 like Orange, and 2 like both, there are only 18 people total (\(10+10-2\)), not 20.
8. Derangements
A Derangement (denoted as \(D_n\)) is a specific type of arrangement where nothing is in its original place.
Example: The "Secret Santa" Problem. If 3 people (A, B, and C) buy gifts for each other, a derangement is a situation where NO ONE gets their own gift.
Possible Derangements: (B gets A's, C gets B's, A gets C's) or (C gets A's, A gets B's, B gets C's).
So, \(D_3 = 2\).
For your exam, you usually find these by ad hoc methods—which is a fancy way of saying "listing them out carefully" for small numbers of items.
Quick Review Box
• Picking a team? Use \(_nC_r\).
• Picking a President and VP? Use \(_nP_r\).
• Objects must be apart? Use the Gap Method.
• Overlapping groups? Use Inclusion-Exclusion.
• Nothing in its right place? That's a Derangement (\(D_n\)).