Discrete math studies objects that are counted, listed, connected, or arranged in separate steps. This cheat sheet helps students organize the core tools used in computer science, data analysis, scheduling, networks, and decision making. It focuses on clear rules for sets, logic, counting, graphs, and sequences.
These ideas support problem solving when quantities are whole, finite, or structured rather than continuous.
The most important skills are describing sets, applying logical statements, counting outcomes without listing every case, and modeling relationships with graphs. Counting formulas such as n!, nPr, and nCr help solve arrangement and selection problems. Graph vocabulary such as vertex, edge, degree, path, and cycle helps describe networks.
Sequences and recurrence rules show how patterns grow from one step to the next.
Key Facts
- The union of two sets includes all elements in either set, written A union B.
- The intersection of two sets includes only elements in both sets, written A intersection B.
- The complement of a set A includes all elements in the universal set that are not in A, written A'.
- The multiplication principle says that if one task has m choices and the next has n choices, then both tasks have m x n total outcomes.
- A permutation counts ordered arrangements, and nPr = n! / (n - r)!.
- A combination counts unordered selections, and nCr = n! / (r! (n - r)!).
- In a finite graph, the sum of all vertex degrees equals 2E, where E is the number of edges.
- An arithmetic sequence has common difference d and formula a_n = a_1 + (n - 1)d.
Vocabulary
- Set
- A set is a well-defined collection of distinct objects called elements.
- Proposition
- A proposition is a statement that is either true or false, but not both.
- Permutation
- A permutation is an arrangement of objects where order matters.
- Combination
- A combination is a selection of objects where order does not matter.
- Graph
- A graph is a structure made of vertices connected by edges.
- Recurrence Relation
- A recurrence relation defines each term of a sequence using one or more earlier terms.
Common Mistakes to Avoid
- Using a permutation when order does not matter is wrong because it counts the same group multiple times in different orders.
- Using a combination when order matters is wrong because it ignores different arrangements that should be counted separately.
- Forgetting the factorial meaning in n! is wrong because n! means n x (n - 1) x (n - 2) x ... x 1, not n squared or n times 10.
- Counting overlapping sets by simple addition is wrong because elements in both sets get counted twice unless the intersection is subtracted.
- Assuming every graph path is a cycle is wrong because a cycle must start and end at the same vertex without repeating other vertices.
Practice Questions
- 1 A password uses 2 letters followed by 3 digits. If letters and digits can repeat, how many passwords are possible?
- 2 How many ways can 4 students be chosen from a group of 12 students for a committee?
- 3 Find the 10th term of the arithmetic sequence 7, 11, 15, 19, ...
- 4 Explain whether arranging 5 books on a shelf should be modeled with a permutation or a combination, and justify your choice.
Understanding Discrete Math Fundamentals
A set is useful because it gives a precise way to sort information. The important part is deciding what counts as an element and what the universal set includes. If a school survey records students who play a sport, the universal set might be every student surveyed, not every student in the country.
This boundary changes the answer to a complement problem. Venn diagrams help students see overlaps, but they can hide a common error. When two groups overlap, adding their sizes counts the shared members twice.
The inclusion exclusion rule fixes this by subtracting the overlap once. This idea appears in surveys, database searches, and probability problems.
Logic is the language used to test whether a claim follows from known facts. A conditional statement has a condition and a result. It fails only when the condition is true but the result is false.
This can feel strange at first. The statement if a figure is a square, then it has four sides is not disproved by a triangle, because the triangle never met the condition. Truth tables make these cases visible.
They are especially helpful with words such as not, if, only if, and either or. In everyday rules, only if points toward a necessary condition. For example, a student may enter only if they have a pass means having a pass is required for entry.
Counting problems depend on reading the restrictions before choosing a method. Order matters when assigning first, second, and third place, creating a password, or seating people in chairs. Order does not matter when choosing a committee or selecting toppings from a list.
A factorial grows very quickly, so calculators are useful for larger cases. Many errors come from treating repeated objects as different. The letters in the word LEVEL cannot be arranged as if all five letters were unique.
Another frequent issue is impossible choices. A code may not begin with zero, or a team may need at least one senior. Break the task into cases when restrictions change from one part of the problem to another.
Graphs turn a relationship into a model that can be inspected. A vertex can represent a person, place, task, or webpage. An edge represents a connection, route, dependency, or friendship.
The degree of a vertex tells how many connections it has. Every edge touches two ends, which explains why adding all degrees counts each edge twice. This gives a quick check for errors in a drawing.
Paths matter in map apps and delivery routes. Cycles matter in electrical circuits, repeated task dependencies, and social networks. A sequence describes values at numbered positions, while a recurrence rule builds each new value from earlier values.
Arithmetic sequences model steady change, such as saving the same amount each week. Recurrences often model growth that depends on what already exists, such as a population with a fixed pattern of reproduction. Students should always state the first term and the starting index, since different starting choices can produce different formulas.