Welcome to Mathematical Preliminaries!
Welcome to the first step in your Discrete Mathematics journey! If you are used to the "smooth" maths of curves and calculus, Discrete Mathematics might feel a bit different. Instead of looking at continuous lines, we look at individual, separate objects—like how many ways you can arrange books on a shelf or how to find the shortest route for a delivery driver.
Don't worry if these concepts feel a bit abstract at first. This chapter is your "toolbox." We are going to learn the basic language and counting tricks that will make the rest of the course much easier. Let's dive in!
1. The Four Types of Problems
In Discrete Mathematics, almost every problem you face will fall into one of these four categories. Think of these as the "goals" of your mathematical mission.
Existence
Does a solution even exist? Before you spend hours trying to find a perfect schedule or a specific route, you first ask: "Is this even possible?"
Construction
If a solution exists, how do we build it? This is about creating a step-by-step method (an algorithm) to get the result.
Enumeration
How many solutions are there? This is all about counting. We don't necessarily need to see all the solutions; we just need to know the total number of possibilities. (e.g., "How many different 4-digit PINs can I create?")
Optimisation
If there are many solutions, which one is the "best"? Usually, this means finding the cheapest, fastest, or shortest way to do something.
Quick Review:
• Existence: Is it possible?
• Construction: How do I do it?
• Enumeration: How many ways?
• Optimisation: Which is the best way?
2. Sets and Partitions
A set is just a collection of objects (called elements). In this chapter, we focus on partitions.
What is a Partition?
Imagine you have a bag of 10 different marbles and you want to put them into three smaller boxes. To be a true partition, you must follow two rules:
1. Every marble must go into a box (no marble is left behind).
2. No marble can be in more than one box at the same time.
Analogy: Think of a school. Every student is assigned to a "House" (like Gryffindor or Ravenclaw). Since every student has a house and no student is in two houses, the houses partition the school population.
Common Mistake: Forgetting that a partition must cover everything. If you divide a set of numbers {1, 2, 3, 4, 5} into {1, 2} and {4, 5}, it's not a partition because you forgot the number 3!
3. The Pigeonhole Principle
This is a surprisingly powerful rule that is very easy to understand.
The Rule: If you have \(n\) items and you try to put them into \(m\) containers, and \(n > m\), then at least one container must hold more than one item.
Example: If there are 8 pigeons and only 7 pigeonholes, at least one hole must have at least 2 pigeons in it.
Did you know? In a city like London, there are definitely at least two people with the exact same number of hairs on their heads! Why? Because the maximum number of hairs a human can have is about 150,000, but there are millions of people in London. Pigeons = People; Holes = Number of hairs.
Key Takeaway: Use the Pigeonhole Principle when you need to prove that a "collision" or "overlap" must happen.
4. Counting: Arrangements and Selections
This is the "Enumeration" part of the course. It helps us count large numbers of possibilities without listing them all.
The Multiplicative Principle
If you have to make a series of choices, you multiply the number of options for each choice together.
Example: If you have 3 shirts and 4 pairs of trousers, you have \(3 \times 4 = 12\) possible outfits.
Permutations (Order Matters!)
A permutation is an ordered arrangement. Use this when the sequence is important, like a race result or a password.
The number of ways to arrange \(n\) distinct objects is \(n!\) (n factorial).
\(n! = n \times (n-1) \times (n-2) \times ... \times 1\).
If you are picking only \(r\) objects from \(n\) total objects where order matters, we use the notation:
\(nPr = \frac{n!}{(n-r)!}\)
Combinations (Order Doesn't Matter!)
A combination is a selection where the order does not matter. Think of choosing a team or toppings for a pizza.
If you are picking \(r\) objects from \(n\) total objects where order doesn't matter, we use the notation:
\(nCr = \frac{n!}{r!(n-r)!}\)
Memory Trick:
• Permutation = Place (Order) matters.
• Combination = Choice (Order doesn't matter).
Handling Restrictions
Sometimes the problem adds "rules," like "The two 2s cannot be next to each other."
1. Repetition: If you have identical items (like the letters in "APPLE"), you divide the total arrangements by the factorial of the repeated items. For APPLE: \(\frac{5!}{2!}\) because there are two 'P's.
2. Restrictions: If two items must not be together, it's often easiest to find the total arrangements and subtract the arrangements where they are together.
5. The Inclusion-Exclusion Principle
When counting things in two different groups, we sometimes accidentally count the people in the "overlap" twice. This principle fixes that.
For two sets \(A\) and \(B\), the number of elements in either \(A\) or \(B\) (the union) is:
\(n(A \cup B) = n(A) + n(B) - n(A \cap B)\)
Analogy: If 10 students play Football (\(A\)) and 12 play Basketball (\(B\)), and 3 play both, how many students play a sport?
It's not \(10 + 12 = 22\), because those 3 students were counted in both groups!
Correct answer: \(10 + 12 - 3 = 19\).
Quick Review: Always subtract the intersection (\(A \cap B\)) so you don't double-count the overlap!
Summary: Chapter Takeaways
• Discrete means separate objects, not smooth lines.
• Use nPr for arrangements (order matters) and nCr for selections (order doesn't matter).
• Factorials (\(n!\)) are for arranging everything in a line.
• The Pigeonhole Principle proves that overlaps must happen when you have more "pigeons" than "holes."
• A Partition splits a set into non-overlapping pieces that cover everything.