Study guide

14.1 Logic, Set Theory, Algorithms, and Combinatorics

GRE Subject Test: Mathematics Exam

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Single-Variable Differential Calculus

1.1 Limits, Continuity, and Epsilon-Delta Definitions 1.2 Differentiation Rules, Implicit & Inverse Differentiation 1.3 Mean Value Theorem, Rolle's Theorem, and Function Extrema 1.4 L'Hôpital's Rule, Curve Sketching, and Optimization 1.5 Functions, Graphs, Transformations, and Inverses 1.6 Trigonometric Functions, Identities, and Equations 1.7 Coordinate Geometry, Lines, Circles, and Conics 1.8 Parametric and Polar Curves

2 Chapter 2: Single-Variable Integral Calculus

2.1 Riemann Sums and the Fundamental Theorem of Calculus 2.2 Advanced Integration Techniques 2.3 Geometric Applications: Areas, Volumes, and Arc Length 2.4 Improper Integrals and Convergence Criteria

3 Chapter 3: Sequences, Infinite Series & Power Series

3.1 Sequences, Monotonicity, and Limits 3.2 Infinite Series and Convergence Tests 3.3 Power Series, Radius and Interval of Convergence 3.4 Taylor and Maclaurin Series with Error Bounds

4 Chapter 4: Multivariable Differential Calculus

4.1 Multivariable Functions, Limits, and Partial Derivatives 4.2 Directional Derivatives, Gradients, and Tangent Planes 4.3 Multivariable Chain Rule and Implicit Differentiation 4.4 Multivariable Extrema, Hessian Matrix, and Lagrange Multipliers

5 Chapter 5: Multivariable Integration & Vector Calculus

5.1 Multiple Integrals in Cylindrical and Spherical Coordinates 5.2 Change of Variables and the Jacobian Determinant 5.3 Vector Fields, Line Integrals, and Green's Theorem 5.4 Surface Integrals, Stokes' Theorem, and the Divergence Theorem

6 Chapter 6: Ordinary Differential Equations

6.1 First-Order ODEs: Separable, Linear, and Exact Equations 6.2 Special First-Order ODEs: Homogeneous, Bernoulli, and Orthogonal Trajectories 6.3 Second-Order Linear Homogeneous ODEs with Constant Coefficients 6.4 Nonhomogeneous Linear ODEs: Undetermined Coefficients and Variation of Parameters

7 Chapter 7: Elementary Algebra & Number Theory

7.1 Elementary Algebra, Polynomials, Roots, and Factorization 7.2 Divisibility, Primes, and the Euclidean Algorithm 7.3 Modular Arithmetic, Chinese Remainder Theorem, and Euler's Totient

8 Chapter 8: Linear Algebra: Vector Spaces & Transformations

8.1 Vector Spaces, Subspaces, Span, and Linear Independence 8.2 Basis, Dimension, and Coordinate Representations 8.3 Linear Transformations, Kernel, Range, and the Rank-Nullity Theorem 8.4 Matrix Representations of Transformations and Change of Basis

9 Chapter 9: Linear Algebra: Matrices, Determinants & Spectral Theory

9.1 Systems of Linear Equations, Matrix Rank, and Row Reduction 9.2 Determinants, Matrix Inverses, and Cramer's Rule 9.3 Eigenvalues, Eigenvectors, and Diagonalization 9.4 Inner Product Spaces, Gram-Schmidt, and the Spectral Theorem

10 Chapter 10: Abstract Algebra: Groups, Rings & Fields

10.1 Groups, Subgroups, and Permutations 10.2 Cosets, Lagrange's Theorem, Normal Subgroups, and Homomorphisms 10.3 Rings, Ideals, Modules, Polynomial Rings, and Fields

11 Chapter 11: Introductory Real Analysis

11.1 The Real Field and Metric Space Topology 11.2 Compactness, Completeness, and Connectedness in R^n 11.3 Continuity, Uniform Continuity, and Value Theorems 11.4 Sequences and Series of Functions: Pointwise and Uniform Convergence

12 Chapter 12: Complex Analysis

12.1 Complex Numbers and Analytic Functions 12.2 Contour Integration and Cauchy's Theorems 12.3 Laurent Series, Singularities, and the Residue Theorem

13 Chapter 13: Topology, Geometry & Numerical Analysis

13.1 Topological Spaces, Open/Closed Sets, and Bases 13.2 Euclidean Geometry, Similarity, Circles, and Transformations 13.3 Numerical Analysis: Error, Root Finding, Interpolation, and Quadrature

14 Chapter 14: Probability, Statistics & Discrete Mathematics

14.1 Logic, Set Theory, Algorithms, and Combinatorics 14.2 Graph Theory: Trees, Cycles, Paths, and Planarity 14.3 Probability Spaces, Conditional Probability, and Bayes' Theorem 14.4 Random Variables, Expected Value, Variance, and Common Distributions

14.1 Logic, Set Theory, Algorithms, and Combinatorics

Key Takeaways Explain This Topic AI

The stars-and-bars method establishes that the number of non-negative integer solutions to x_1 + ... + x_k = n is C(n+k-1, k-1), whereas strictly positive integer solutions number C(n-1, k-1).

The Principle of Inclusion-Exclusion calculates the size of arbitrary finite unions and yields the derangement formula D_n = n! sum_{k=0}^n (-1)^k / k! ~ n! / e, which satisfies the recurrence D_n = (n-1)(D_{n-1} + D_{n-2}).

The generalized Pigeonhole Principle states that if N items occupy k boxes, at least one box contains at least ceil(N/k) items, providing sharp existence proofs in modular arithmetic and geometric configurations.

Linear homogeneous recurrence relations with constant coefficients are solved via the roots of the characteristic polynomial, with root multiplicity m introducing polynomial factors (C_0 + C_1 n + ... + C_{m-1} n^{m-1}) r^n.

Propositional equivalences, quantifier negation, set operations, relations, functions, and asymptotic algorithm analysis form the logical framework in which discrete proofs and counting arguments operate.

Last updated: September 2026

14.1 Combinatorics, Binomial Coefficients, and Pigeonhole Principle

Combinatorics on the GRE Mathematics Subject Test evaluates enumerative methods, algebraic identities of binomial coefficients, partition models, the Principle of Inclusion-Exclusion (PIE), the Pigeonhole Principle (PHP), and linear recurrence relations. Mastery of these counting principles and algebraic structures is vital for rapid problem solving.

Permutations, Combinations, and Binomial Identities

For a finite set of n n n distinct elements:

Permutations ( k k k -arrangements): P ( n , k ) = n ! ( n − k ) ! P(n, k) = \frac{n!}{(n-k)!} P ( n , k ) = ( n − k )! n ! ​

Combinations ( k k k -subsets): ( n k ) = n ! k ! ( n − k ) ! \binom{n}{k} = \frac{n!}{k!(n-k)!} ( k n ​ ) = k ! ( n − k )! n ! ​

Fundamental Binomial Identities

Symmetry & Pascal's Recurrence: ( n k ) = ( n n − k ) \binom{n}{k} = \binom{n}{n-k} ( k n ​ ) = ( n − k n ​ ) and ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} ( k n ​ ) = ( k − 1 n − 1 ​ ) + ( k n − 1 ​ )

Binomial Theorem: For any x , y ∈ R x, y \in \mathbb{R} x , y ∈ R : ( x + y ) n = ∑ k = 0 n ( n k ) x n − k y k (x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k ( x + y ) n = k = 0 ∑ n ​ ( k n ​ ) x n − k y k Standard specializations include ∑ k = 0 n ( n k ) = 2 n \sum_{k=0}^n \binom{n}{k} = 2^n ∑ k = 0 n ​ ( k n ​ ) = 2 n , ∑ k = 0 n ( − 1 ) k ( n k ) = 0 \sum_{k=0}^n (-1)^k \binom{n}{k} = 0 ∑ k = 0 n ​ ( − 1 ) k ( k n ​ ) = 0 , and ∑ k = 0 n k ( n k ) = n 2 n − 1 \sum_{k=0}^n k \binom{n}{k} = n 2^{n-1} ∑ k = 0 n ​ k ( k n ​ ) = n 2 n − 1 .

Chu-Vandermonde Identity: ∑ j = 0 k ( m j ) ( n k − j ) = ( m + n k ) \sum_{j=0}^k \binom{m}{j} \binom{n}{k-j} = \binom{m+n}{k} ∑ j = 0 k ​ ( j m ​ ) ( k − j n ​ ) = ( k m + n ​ )

Hockey-Stick Identity: ∑ i = r n ( i r ) = ( n + 1 r + 1 ) \sum_{i=r}^n \binom{i}{r} = \binom{n+1}{r+1} ∑ i = r n ​ ( r i ​ ) = ( r + 1 n + 1 ​ )

Multinomial Theorem and Integer Partitions

Distributing n n n distinct elements into r r r distinct labeled categories of sizes k 1 , … , k r k_1, \dots, k_r k 1 ​ , … , k r ​ with ∑ k i = n \sum k_i = n ∑ k i ​ = n is given by the multinomial coefficient: ( n k 1 , k 2 , … , k r ) = n ! k 1 ! k 2 ! ⋯ k r ! \binom{n}{k_1, k_2, \dots, k_r} = \frac{n!}{k_1! k_2! \cdots k_r!} ( k 1 ​ , k 2 ​ , … , k r ​ n ​ ) = k 1 ​ ! k 2 ​ ! ⋯ k r ​ ! n ! ​

The multinomial expansion is: ( x 1 + x 2 + ⋯ + x r ) n = ∑ k 1 + ⋯ + k r = n ( n k 1 , … , k r ) x 1 k 1 ⋯ x r k r (x_1 + x_2 + \dots + x_r)^n = \sum_{k_1 + \dots + k_r = n} \binom{n}{k_1, \dots, k_r} x_1^{k_1} \cdots x_r^{k_r} ( x 1 ​ + x 2 ​ + ⋯ + x r ​ ) n = k 1 ​ + ⋯ + k r ​ = n ∑ ​ ( k 1 ​ , … , k r ​ n ​ ) x 1 k 1 ​ ​ ⋯ x r k r ​ ​

The number of distinct monomials in this expansion is ( n + r − 1 r − 1 ) \binom{n+r-1}{r-1} ( r − 1 n + r − 1 ​ ) .

Stars and Bars (Balls and Urns)

The stars-and-bars method counts compositions of integers, equivalent to placing n n n indistinguishable objects into k k k distinguishable bins:

Non-Negative Solutions ( x i ≥ 0 x_i \ge 0 x i ​ ≥ 0 ): The number of integer solutions to x 1 + ⋯ + x k = n x_1 + \dots + x_k = n x 1 ​ + ⋯ + x k ​ = n is ( n + k − 1 k − 1 ) \binom{n + k - 1}{k - 1} ( k − 1 n + k − 1 ​ ) .

Positive Solutions ( x i ≥ 1 x_i \ge 1 x i ​ ≥ 1 ): Substituting y i = x i − 1 ≥ 0 y_i = x_i - 1 \ge 0 y i ​ = x i ​ − 1 ≥ 0 gives y 1 + ⋯ + y k = n − k y_1 + \dots + y_k = n - k y 1 ​ + ⋯ + y k ​ = n − k , yielding ( n − 1 k − 1 ) \binom{n - 1}{k - 1} ( k − 1 n − 1 ​ ) .

General Lower Bounds ( x i ≥ c i x_i \ge c_i x i ​ ≥ c i ​ ): Substituting y i = x i − c i ≥ 0 y_i = x_i - c_i \ge 0 y i ​ = x i ​ − c i ​ ≥ 0 gives ∑ y i = n − ∑ c i \sum y_i = n - \sum c_i ∑ y i ​ = n − ∑ c i ​ .

Principle of Inclusion-Exclusion and Derangements

For finite subsets A 1 , … , A n A_1, \dots, A_n A 1 ​ , … , A n ​ of a universe U U U : ∣ A 1 ∪ ⋯ ∪ A n ∣ = ∑ i ∣ A i ∣ − ∑ i < j ∣ A i ∩ A j ∣ + ⋯ + ( − 1 ) n − 1 ∣ A 1 ∩ ⋯ ∩ A n ∣ |A_1 \cup \dots \cup A_n| = \sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n| ∣ A 1 ​ ∪ ⋯ ∪ A n ​ ∣ = i ∑ ​ ∣ A i ​ ∣ − i < j ∑ ​ ∣ A i ​ ∩ A j ​ ∣ + ⋯ + ( − 1 ) n − 1 ∣ A 1 ​ ∩ ⋯ ∩ A n ​ ∣

The count of elements satisfying none of properties A 1 , … , A n A_1, \dots, A_n A 1 ​ , … , A n ​ is: ∣ U ∖ ⋃ i = 1 n A i ∣ = ∣ U ∣ − ∑ ∣ A i ∣ + ∑ ∣ A i ∩ A j ∣ − ⋯ + ( − 1 ) n ∣ A 1 ∩ ⋯ ∩ A n ∣ |U \setminus \bigcup_{i=1}^n A_i| = |U| - \sum |A_i| + \sum |A_i \cap A_j| - \dots + (-1)^n |A_1 \cap \dots \cap A_n| ∣ U ∖ i = 1 ⋃ n ​ A i ​ ∣ = ∣ U ∣ − ∑ ∣ A i ​ ∣ + ∑ ∣ A i ​ ∩ A j ​ ∣ − ⋯ + ( − 1 ) n ∣ A 1 ​ ∩ ⋯ ∩ A n ​ ∣

Derangements

A derangement is a permutation σ ∈ S n \sigma \in S_n σ ∈ S n ​ with no fixed points ( σ ( i ) ≠ i \sigma(i) \neq i σ ( i )  = i for all i i i ). By PIE: D n = n ! ∑ k = 0 n ( − 1 ) k k ! = n ! ( 1 − 1 + 1 2 ! − ⋯ + ( − 1 ) n n ! ) D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} = n! \left( 1 - 1 + \frac{1}{2!} - \dots + \frac{(-1)^n}{n!} \right) D n ​ = n ! k = 0 ∑ n ​ k ! ( − 1 ) k ​ = n ! ( 1 − 1 + 2 ! 1 ​ − ⋯ + n ! ( − 1 ) n ​ )

As n → ∞ n \to \infty n → ∞ , D n / n ! → e − 1 ≈ 0.3679 D_n / n! \to e^{-1} \approx 0.3679 D n ​ / n ! → e − 1 ≈ 0.3679 . The derangement numbers satisfy the recurrences: D n = ( n − 1 ) ( D n − 1 + D n − 2 ) , D n = n D n − 1 + ( − 1 ) n D_n = (n-1)(D_{n-1} + D_{n-2}), \qquad D_n = n D_{n-1} + (-1)^n D n ​ = ( n − 1 ) ( D n − 1 ​ + D n − 2 ​ ) , D n ​ = n D n − 1 ​ + ( − 1 ) n

with initial terms D 1 = 0 , D 2 = 1 , D 3 = 2 , D 4 = 9 , D 5 = 44 D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44 D 1 ​ = 0 , D 2 ​ = 1 , D 3 ​ = 2 , D 4 ​ = 9 , D 5 ​ = 44 .

The Pigeonhole Principle (PHP)

Basic PHP: If N N N items occupy k k k boxes and N > k N > k N > k , at least one box contains ≥ 2 \ge 2 ≥ 2 items.

Generalized PHP: If N N N items occupy k k k boxes, at least one box contains ≥ ⌈ N / k ⌉ \ge \lceil N/k \rceil ≥ ⌈ N / k ⌉ items.

Applications: Finding identical remainders modulo m m m among m + 1 m+1 m + 1 integers, bounding pairwise distances of points in compact sets, and Ramsey number bounds (such as R ( 3 , 3 ) = 6 R(3,3) = 6 R ( 3 , 3 ) = 6 ).

Linear Recurrence Relations

A homogeneous linear recurrence of order k k k with constant coefficients has the form: a n + c 1 a n − 1 + ⋯ + c k a n − k = 0 a_n + c_1 a_{n-1} + \dots + c_k a_{n-k} = 0 a n ​ + c 1 ​ a n − 1 ​ + ⋯ + c k ​ a n − k ​ = 0

Its characteristic polynomial is P ( r ) = r k + c 1 r k − 1 + ⋯ + c k = 0 P(r) = r^k + c_1 r^{k-1} + \dots + c_k = 0 P ( r ) = r k + c 1 ​ r k − 1 + ⋯ + c k ​ = 0 .

Distinct Roots: If roots r 1 , … , r k r_1, \dots, r_k r 1 ​ , … , r k ​ are distinct, the general solution is a n = ∑ i = 1 k C i r i n a_n = \sum_{i=1}^k C_i r_i^n a n ​ = ∑ i = 1 k ​ C i ​ r i n ​ .

Repeated Roots: A root r r r of multiplicity m m m contributes ( C 0 + C 1 n + ⋯ + C m − 1 n m − 1 ) r n (C_0 + C_1 n + \dots + C_{m-1} n^{m-1}) r^n ( C 0 ​ + C 1 ​ n + ⋯ + C m − 1 ​ n m − 1 ) r n .

Non-Homogeneous Recurrences: For a n + c 1 a n − 1 = f ( n ) a_n + c_1 a_{n-1} = f(n) a n ​ + c 1 ​ a n − 1 ​ = f ( n ) , solve a n = a n ( h ) + a n ( p ) a_n = a_n^{(h)} + a_n^{(p)} a n ​ = a n ( h ) ​ + a n ( p ) ​ using undetermined coefficients.

Combinatorial Counting Reference Table

Model Object Nature Bin / Group Type Formula

Ordered Selections Distinct Distinct (no replacement) P ( n , k ) = n ! ( n − k ) ! P(n, k) = \frac{n!}{(n-k)!} P ( n , k ) = ( n − k )! n ! ​

Unordered Selections Distinct Distinct (no replacement) ( n k ) = n ! k ! ( n − k ) ! \binom{n}{k} = \frac{n!}{k!(n-k)!} ( k n ​ ) = k ! ( n − k )! n ! ​

Multinomial Partitions Distinct Labeled Categories ( n k 1 , … , k r ) = n ! ∏ k i ! \binom{n}{k_1, \dots, k_r} = \frac{n!}{\prod k_i!} ( k 1 ​ , … , k r ​ n ​ ) = ∏ k i ​ ! n ! ​

Stars & Bars ( x i ≥ 0 x_i \ge 0 x i ​ ≥ 0 ) Indistinguishable Distinguishable ( n + k − 1 k − 1 ) \binom{n+k-1}{k-1} ( k − 1 n + k − 1 ​ )

Stars & Bars ( x i ≥ 1 x_i \ge 1 x i ​ ≥ 1 ) Indistinguishable Distinguishable ( n − 1 k − 1 ) \binom{n-1}{k-1} ( k − 1 n − 1 ​ )

Derangements Distinct Fixed-point free D n = n ! ∑ j = 0 n ( − 1 ) j j ! D_n = n! \sum_{j=0}^n \frac{(-1)^j}{j!} D n ​ = n ! ∑ j = 0 n ​ j ! ( − 1 ) j ​

Step-by-Step Worked Problem

Problem: How many integer solutions satisfy x 1 + x 2 + x 3 + x 4 = 20 x_1 + x_2 + x_3 + x_4 = 20 x 1 ​ + x 2 ​ + x 3 ​ + x 4 ​ = 20 subject to 1 ≤ x 1 , x 2 ≤ 6 1 \le x_1, x_2 \le 6 1 ≤ x 1 ​ , x 2 ​ ≤ 6 and x 3 , x 4 ≥ 0 x_3, x_4 \ge 0 x 3 ​ , x 4 ​ ≥ 0 ?

Solution:

Shift lower bounds: Set y 1 = x 1 − 1 ≥ 0 y_1 = x_1 - 1 \ge 0 y 1 ​ = x 1 ​ − 1 ≥ 0 and y 2 = x 2 − 1 ≥ 0 y_2 = x_2 - 1 \ge 0 y 2 ​ = x 2 ​ − 1 ≥ 0 . The conditions become 0 ≤ y 1 , y 2 ≤ 5 0 \le y_1, y_2 \le 5 0 ≤ y 1 ​ , y 2 ​ ≤ 5 and x 3 , x 4 ≥ 0 x_3, x_4 \ge 0 x 3 ​ , x 4 ​ ≥ 0 .

Transform equation: ( y 1 + 1 ) + ( y 2 + 1 ) + x 3 + x 4 = 20 ⟹ y 1 + y 2 + x 3 + x 4 = 18 (y_1 + 1) + (y_2 + 1) + x_3 + x_4 = 20 \implies y_1 + y_2 + x_3 + x_4 = 18 ( y 1 ​ + 1 ) + ( y 2 ​ + 1 ) + x 3 ​ + x 4 ​ = 20 ⟹ y 1 ​ + y 2 ​ + x 3 ​ + x 4 ​ = 18 .

Unrestricted non-negative count: By stars and bars, ( 18 + 4 − 1 4 − 1 ) = ( 21 3 ) = 1330 \binom{18 + 4 - 1}{4 - 1} = \binom{21}{3} = 1330 ( 4 − 1 18 + 4 − 1 ​ ) = ( 3 21 ​ ) = 1330 .

Violations via PIE:

Let A 1 A_1 A 1 ​ be y 1 ≥ 6 y_1 \ge 6 y 1 ​ ≥ 6 : substitute z 1 = y 1 − 6 ≥ 0 ⟹ z 1 + y 2 + x 3 + x 4 = 12 z_1 = y_1 - 6 \ge 0 \implies z_1 + y_2 + x_3 + x_4 = 12 z 1 ​ = y 1 ​ − 6 ≥ 0 ⟹ z 1 ​ + y 2 ​ + x 3 ​ + x 4 ​ = 12 , yielding ∣ A 1 ∣ = ( 12 + 3 3 ) = ( 15 3 ) = 455 |A_1| = \binom{12+3}{3} = \binom{15}{3} = 455 ∣ A 1 ​ ∣ = ( 3 12 + 3 ​ ) = ( 3 15 ​ ) = 455 .

By symmetry, ∣ A 2 ∣ = 455 |A_2| = 455 ∣ A 2 ​ ∣ = 455 for y 2 ≥ 6 y_2 \ge 6 y 2 ​ ≥ 6 .

For A 1 ∩ A 2 A_1 \cap A_2 A 1 ​ ∩ A 2 ​ ( y 1 , y 2 ≥ 6 y_1, y_2 \ge 6 y 1 ​ , y 2 ​ ≥ 6 ): z 1 + z 2 + x 3 + x 4 = 6 z_1 + z_2 + x_3 + x_4 = 6 z 1 ​ + z 2 ​ + x 3 ​ + x 4 ​ = 6 , yielding ∣ A 1 ∩ A 2 ∣ = ( 6 + 3 3 ) = ( 9 3 ) = 84 |A_1 \cap A_2| = \binom{6+3}{3} = \binom{9}{3} = 84 ∣ A 1 ​ ∩ A 2 ​ ∣ = ( 3 6 + 3 ​ ) = ( 3 9 ​ ) = 84 .

Compute valid count: By PIE, ∣ A 1 ∪ A 2 ∣ = 455 + 455 − 84 = 826 |A_1 \cup A_2| = 455 + 455 - 84 = 826 ∣ A 1 ​ ∪ A 2 ​ ∣ = 455 + 455 − 84 = 826 . Valid Solutions = 1330 − 826 = 504 \text{Valid Solutions} = 1330 - 826 = 504 Valid Solutions = 1330 − 826 = 504

GRE Exam Traps & Pitfalls

Trap 1: Indistinguishable vs. Distinguishable Bins Stars and bars applies strictly when bins are distinguishable ( x 1 + x 2 + x 3 = n x_1 + x_2 + x_3 = n x 1 ​ + x 2 ​ + x 3 ​ = n ). If bins are indistinguishable, the problem requires integer partition numbers p ( n ) p(n) p ( n ) or Stirling numbers of the second kind, not binomial coefficients.

Trap 2: Omitting Powers of n n n for Repeated Characteristic Roots When a characteristic root has multiplicity m > 1 m > 1 m > 1 , omitting factors of n j n^j n j ( n r n , n 2 r n n r^n, n^2 r^n n r n , n 2 r n ) produces a defective basis that cannot satisfy arbitrary initial values.

Trap 3: Double Counting Violations in Bounded Stars & Bars Subtracting single-variable upper-bound violations without adding back their intersections over-penalizes the count and violates PIE.

Trap 4: Conflating Strict with Weak Inequality in Compositions Pay careful attention to whether variables satisfy x i ≥ 0 x_i \ge 0 x i ​ ≥ 0 ( ( n + k − 1 k − 1 ) \binom{n+k-1}{k-1} ( k − 1 n + k − 1 ​ ) ) or x i ≥ 1 x_i \ge 1 x i ​ ≥ 1 ( ( n − 1 k − 1 ) \binom{n-1}{k-1} ( k − 1 n − 1 ​ ) ). Shifting bounds before applying stars and bars eliminates indexing errors.

Logic, Set Theory, Relations, and Algorithms

Discrete mathematics begins with precise statements and finite procedures. These ideas support combinatorial proofs and prevent common errors with negation, quantifiers, and asymptotic comparisons.

Propositional logic and quantifiers

An implication p ⇒ q p\Rightarrow q p ⇒ q is false only when p p p is true and q q q is false. It is logically equivalent to ¬ p ∨ q \neg p\lor q ¬ p ∨ q and to its contrapositive ¬ q ⇒ ¬ p \neg q\Rightarrow\neg p ¬ q ⇒ ¬ p , but not to its converse q ⇒ p q\Rightarrow p q ⇒ p . De Morgan's laws are ¬ ( p ∧ q ) ≡ ¬ p ∨ ¬ q , ¬ ( p ∨ q ) ≡ ¬ p ∧ ¬ q . \neg(p\land q)\equiv \neg p\lor\neg q,\qquad

\neg(p\lor q)\equiv \neg p\land\neg q. ¬ ( p ∧ q ) ≡ ¬ p ∨ ¬ q , ¬ ( p ∨ q ) ≡ ¬ p ∧ ¬ q .

Quantifier order matters. The negations are ¬ ( ∀ x P ( x ) ) ≡ ∃ x ¬ P ( x ) , ¬ ( ∃ x P ( x ) ) ≡ ∀ x ¬ P ( x ) . \neg(\forall x\,P(x))\equiv\exists x\,\neg P(x),\qquad

\neg(\exists x\,P(x))\equiv\forall x\,\neg P(x). ¬ ( ∀ x P ( x )) ≡ ∃ x ¬ P ( x ) , ¬ ( ∃ x P ( x )) ≡ ∀ x ¬ P ( x ) .

Thus the negation of “for every real x x x there exists an integer n n n with n > x n>x n > x ” is “there exists a real x x x such that every integer n n n satisfies n ≤ x n\le x n ≤ x .” Each quantifier changes and the predicate is negated.

Standard proof methods include direct proof, contrapositive, contradiction, cases, and induction. Strong induction allows the entire collection of earlier cases in the induction step. To disprove a universal statement, one counterexample suffices; examples cannot prove a universal statement.

Sets, functions, and cardinality

For sets A , B A,B A , B , A ∖ B = A ∩ B c , ( A ∪ B ) c = A c ∩ B c , ( A ∩ B ) c = A c ∪ B c . A\setminus B=A\cap B^c,\qquad

(A\cup B)^c=A^c\cap B^c,\qquad

(A\cap B)^c=A^c\cup B^c. A ∖ B = A ∩ B c , ( A ∪ B ) c = A c ∩ B c , ( A ∩ B ) c = A c ∪ B c .

The Cartesian product A × B A\times B A × B contains ordered pairs, so for finite sets ∣ A × B ∣ = ∣ A ∣ ∣ B ∣ |A\times B|=|A||B| ∣ A × B ∣ = ∣ A ∣∣ B ∣ . The power set P ( A ) \mathcal P(A) P ( A ) contains every subset and has size 2 ∣ A ∣ 2^{|A|} 2 ∣ A ∣ when A A A is finite. Cantor's theorem says there is no surjection A → P ( A ) A\to\mathcal P(A) A → P ( A ) for any set A A A .

A function is injective when equal outputs force equal inputs, surjective when every codomain element is attained, and bijective when both hold. For finite sets of equal size, injective, surjective, and bijective are equivalent. For infinite sets they are not: n ↦ n + 1 n\mapsto n+1 n ↦ n + 1 on the nonnegative integers is injective but not surjective.

Relations and equivalence classes

A relation on A A A is a subset of A × A A\times A A × A . An equivalence relation is reflexive, symmetric, and transitive. Its equivalence classes form a partition of A A A ; conversely, every partition defines an equivalence relation by putting elements in the same block.

A partial order is reflexive, antisymmetric, and transitive. In a poset, two elements need not be comparable. A total order adds comparability. Divisibility on positive integers is a partial order, while congruence modulo n n n is an equivalence relation.

Algorithms, correctness, and growth

An algorithm is a finite, unambiguous procedure. A correctness proof usually establishes a precondition, a loop invariant preserved by each iteration, and a postcondition obtained when the loop terminates. Termination needs a quantity that moves monotonically toward a bound, such as a nonnegative integer that strictly decreases.

Big-O gives an eventual upper bound: f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f ( n ) = O ( g ( n )) if constants C , n 0 > 0 C,n_0>0 C , n 0 ​ > 0 exist with ∣ f ( n ) ∣ ≤ C ∣ g ( n ) ∣ |f(n)|\le C|g(n)| ∣ f ( n ) ∣ ≤ C ∣ g ( n ) ∣ for n ≥ n 0 n\ge n_0 n ≥ n 0 ​ . Big-Omega is an eventual lower bound, and Big-Theta means both. Constant factors and lower-order terms disappear, so 3 n 2 + 7 n + 4 = Θ ( n 2 ) 3n^2+7n+4=\Theta(n^2) 3 n 2 + 7 n + 4 = Θ ( n 2 ) . The usual growth hierarchy is 1 ≺ log ⁡ n ≺ n a ≺ b n ≺ n ! 1\prec\log n\prec n^a\prec b^n\prec n! 1 ≺ lo g n ≺ n a ≺ b n ≺ n !

for fixed a > 0 a>0 a > 0 and b > 1 b>1 b > 1 .

A loop performing constant work n n n times is Θ ( n ) \Theta(n) Θ ( n ) . Two nested loops each running n n n times are usually Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) . Repeatedly halving the problem size produces Θ ( log ⁡ n ) \Theta(\log n) Θ ( lo g n ) iterations, which explains binary search. Correctness and running time are different claims: a fast algorithm may be wrong, and a correct algorithm may be inefficient.

Worked example

Consider Euclid's algorithm: while b ≠ 0 b\ne0 b  = 0 , replace ( a , b ) (a,b) ( a , b ) by ( b , a m o d b ) (b,a\bmod b) ( b , a mod b ) . The invariant is gcd ⁡ ( a , b ) = gcd ⁡ ( b , a m o d b ) \gcd(a,b)=\gcd(b,a\bmod b) g cd ( a , b ) = g cd ( b , a mod b ) . The second nonnegative coordinate strictly decreases, so the process terminates. At termination b = 0 b=0 b = 0 , and the invariant gives the answer gcd ⁡ ( a , 0 ) = ∣ a ∣ \gcd(a,0)=|a| g cd ( a , 0 ) = ∣ a ∣ .

Common traps

The converse is not the contrapositive. Negating a quantified statement changes every quantifier. Antisymmetry does not mean “not symmetric.” Big-O is not exact equality, and an upper bound need not be tight. A loop invariant must hold before the loop, remain true after each iteration, and imply the desired result at termination.

Loading diagram... Combinatorial Counting Strategy Selection