Discrete Mathematics: Sets, Relations, Combinatorics and

Discrete mathematics studies objects that come in separate, countable chunks rather than smooth continua: integers instead of real numbers, graphs instead of curves, true-or-false instead of shades of grey. Its core topics are sets, logic, relations, combinatorics, and graphs.

It matters because computers are discrete machines. Every algorithm, database query, network route, and encryption scheme rests on discrete structures. While calculus models the physical world, discrete mathematics models the digital one, making it the native language of computer science and engineering.

Key Concepts

• Set: an unordered collection of distinct objects, like {1, 2, 3}. Operations include union, intersection, and complement.
• Relation: a set of ordered pairs linking elements of sets. Special types: reflexive, symmetric, transitive; an equivalence relation has all three.
• Function: a relation assigning each input exactly one output. Injective means one-to-one, surjective means onto, bijective means both.
• Permutation: an ordered arrangement of objects. Order matters.
• Combination: an unordered selection of objects. Order does not matter.
• Graph: a set of vertices joined by edges. Models networks of all kinds.
• Degree: the number of edges touching a vertex. The handshake lemma says the sum of all degrees equals twice the number of edges.

Formulas

• Permutations: P(n, r) = n! divided by (n minus r)!. Counts ordered selections of r from n.
• Combinations: C(n, r) = n! divided by (r! times (n minus r)!). Counts unordered selections.
• Power set size: a set with n elements has 2^n subsets.
• Inclusion-exclusion: |A union B| = |A| plus |B| minus |A intersect B|.
• Handshake lemma: sum of degrees = 2|E|, where |E| is the number of edges. Hence the number of odd-degree vertices is always even.
• Pigeonhole principle: if more than n items go into n boxes, some box holds at least two items.

Worked Example

A team of 3 must be chosen from 10 engineers, and then a leader picked from the 3. How many outcomes?

1. Choose the team ignoring order: C(10, 3) = 10! divided by (3! times 7!).
2. Compute: (10 times 9 times 8) divided by (3 times 2 times 1) = 720 divided by 6 = 120 teams.
3. Pick the leader from the 3 chosen: 3 choices.
4. Total = 120 times 3 = 360 outcomes.
5. Sanity check with permutations: pick leader first (10 ways), then 2 members from 9: C(9, 2) = 36; 10 times 36 = 360. Matches.

Common Misconceptions

• Permutations and combinations are interchangeable. They differ exactly on whether order matters. Choosing a committee is a combination; assigning president, secretary, treasurer is a permutation.
• Every relation is a function. A function needs exactly one output per input. The relation {(1, 2), (1, 3)} is not a function.
• Infinite sets are all the same size. The integers and the rationals can be matched one-to-one, but the real numbers form a strictly larger infinity, proved by Cantor's diagonal argument.

Real-World Applications

• Algorithms: sorting, searching, and complexity analysis are discrete mathematics in action.
• Databases: tables and queries are built on set theory and relations.
• Networks: routing, social graphs, and the internet itself are modeled as graphs.
• Cryptography: number theory and combinatorics secure online communication.
• Scheduling: timetables and resource allocation reduce to graph coloring and matching problems.

Discrete mathematics gives you sets for collections, logic for reasoning, combinatorics for counting, and graphs for networks. These four tools describe nearly everything a computer does, which is why the subject sits at the heart of every computing degree.