Graduate
  1. Real Analysis  1.1. Set Theory and Logic  1.1.1. Sets and Operations  1.1.2. Relations and Functions  1.1.3. Logic and Quantifiers  1.1.4. Cardinality of Sets  1.2. Metric Spaces  1.2.1. Open and Closed Sets  1.2.2. Convergence of Sequences  1.2.3. Continuous Functions in Metric Spaces  1.2.4. Compactness and Completeness in Metric Spaces in Real Analysis  1.3. Sequence and Series  1.3.1. Convergence of Sequences  1.3.2. Infinite Series  1.3.3. Uniform Convergence  1.3.4. Power Series  1.4. Differentiation  1.4.1. Mean Value Theorems  1.4.2. Taylor Series  1.4.3. Functions of Several Variables  1.4.4. Partial Derivatives  1.5. Integration  1.5.1. Riemann and Lebesgue Integration  1.5.2. Improper Integrals  1.5.3. Measure Theory  1.5.4. Fubini’s Theorem  1.6. Functional Analysis  1.6.1. Banach Spaces  1.6.2. Hilbert Spaces  1.6.3. Operators on Spaces  1.6.4. Spectral Theory
  2. Abstract Algebra  2.1. Groups  2.1.1. Definitions and Examples in Groups in Abstract Algebra  2.1.2. Group Homomorphisms  2.1.3. Normal Subgroups  2.1.4. Sylow Theorems  2.2. Rings and Fields  2.2.1. Ideals and Factor Rings  2.2.2. Field Extensions  2.2.3. Galois Theory  2.2.4. Polynomial Rings  2.3. Modules  2.3.1. Module Homomorphisms  2.3.2. Free Modules  2.3.3. Tensor Products  2.3.4. Exact Sequences  2.4. Linear Algebra  2.4.1. Vector Spaces  2.4.2. Eigenvalues and Eigenvectors  2.4.3. Inner Product Spaces  2.4.4. Diagonalization
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Compactness and Connectedness  3.1.3. Continuous Maps  3.1.4. Separation Axioms  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy and Homology  3.2.3. Simplicial Complexes  3.2.4. Exact Sequences in Homology  3.3. Differential Topology  3.3.1. Manifolds  3.3.2. Smooth Functions  3.3.3. Tangent and Cotangent Spaces  3.3.4. Vector Bundles
  4. Differential Equations  4.1. Ordinary Differential Equations  4.1.1. First-Order Equations  4.1.2. Second-Order Linear Equations  4.1.3. Systems of Differential Equations  4.1.4. Stability Analysis  4.2. Partial Differential Equations  4.2.1. Classification of PDEs  4.2.2. Fourier Series  4.2.3. Green's Functions  4.2.4. Method of Characteristics  4.3. Dynamical Systems  4.3.1. Stability Theory  4.3.2. Limit Cycles  4.3.3. Chaos Theory  4.3.4. Bifurcation Theory
  5. Probability and Statistics  5.1. Probability Theory  5.1.1. Random Variables  5.1.2. Probability Distributions  5.1.3. Law of Large Numbers  5.1.4. Central Limit Theorem  5.2. Statistical Inference  5.2.1. Hypothesis Testing  5.2.2. Confidence Intervals  5.2.3. Bayesian Methods  5.2.4. Maximum Likelihood Estimation  5.3. Stochastic Processes  5.3.1. Markov Chains  5.3.2. Brownian Motion  5.3.3. Poisson Processes  5.3.4. Martingales
  6. Numerical Analysis  6.1. Numerical Solutions of Equations  6.1.1. Root Finding  6.1.2. Iterative Methods  6.1.3. Convergence Analysis  6.1.4. Error Bounds in Numerical Solutions of Equations  6.2. Numerical Linear Algebra  6.2.1. Matrix Factorizations  6.2.2. Eigenvalue Computations  6.2.3. Sparse Matrices  6.2.4. Preconditioning Techniques  6.3. Numerical Integration and Differentiation  6.3.1. Quadrature Methods  6.3.2. Finite Differences  6.3.3. Error Analysis in Numerical Integration and Differentiation  6.3.4. Adaptive Methods
  7. Complex Analysis  7.1. Complex Numbers  7.1.1. Polar Form  7.1.2. Complex Conjugates  7.1.3. Exponential Form  7.1.4. Roots of Unity  7.2. Analytic Functions  7.2.1. Cauchy-Riemann Equations  7.2.2. Power Series  7.2.3. Conformal Mappings  7.2.4. Harmonic Functions  7.3. Integration in the Complex Plane  7.3.1. Cauchy’s Theorem  7.3.2. Residue Theorem  7.3.3. Contour Integration  7.3.4. Integral Transforms
  8. Mathematical Logic and Foundations  8.1. Propositional Logic  8.1.1. Truth Tables  8.1.2. Logical Equivalences  8.1.3. Proof Techniques in Propositional Logic  8.1.4. Resolution  8.2. Predicate Logic  8.2.1. Quantifiers in Predicate Logic  8.2.2. Formal Systems in Predicate Logic  8.2.3. Completeness and Soundness  8.2.4. Model Theory  8.3. Set Theory  8.3.1. Cardinality and Ordinality  8.3.2. Axiomatic Systems  8.3.3. Zermelo-Fraenkel Set Theory  8.3.4. Forcing
  9. Optimization  9.1. Linear Programming  9.1.1. Simplex Method  9.1.2. Duality in Linear Programming  9.1.3. Sensitivity Analysis  9.1.4. Interior Point Methods  9.2. Nonlinear Programming  9.2.1. Gradient Descent  9.2.2. Lagrange Multipliers  9.2.3. Convex Optimization  9.2.4. Quadratic Programming  9.3. Combinatorial Optimization  9.3.1. Graph Algorithms  9.3.2. Integer Programming  9.3.3. Network Flows  9.3.4. Approximation Algorithms
  10. Discrete Mathematics  10.1. Graph Theory  10.1.1. Graph Representations  10.1.2. Planarity and Coloring  10.1.3. Shortest Path Algorithms  10.1.4. Network Flows  10.2. Combinatorics  10.2.1. Permutations and Combinations  10.2.2. Generating Functions  10.2.3. Recurrence Relations  10.2.4. Inclusion-Exclusion Principle  10.3. Cryptography  10.3.1. Number Theory Applications in Cryptography  10.3.2. Symmetric and Asymmetric Cryptography  10.3.3. RSA and Elliptic Curve Cryptography  10.3.4. Post-Quantum Cryptography

Graduate → Discrete Mathematics ↓


Combinatorics


Combinatorics is a fascinating area of discrete mathematics that deals with the counting, arrangement, and structure of elements within a set. While often related to probability, combinatorics itself does not inherently involve any notion of uncertainty. Instead, it provides a toolkit of methods and theories that offer a rigorous means for addressing questions involving discrete structures and finite collections.

Basic principles

Rule of sum

The law of addition, or the sum principle, states that if you have two non-overlapping categories, and one category can occur in n ways and the other in m ways, then there are n + m ways for either of the two events to occur.

For example:

If there are 3 different routes from city A to city B and 4 different routes from city A to city C, and no route goes to both B and C,
So you can choose the route to city B or city C in 3 + 4 = 7 ways.
Route to B (3 routes) Route to C (4 routes) Total = 3 + 4 = 7 ways

Rule of product

The law of multiplication, or the multiplication principle, asserts that if there are n ways to do one task, and m ways to do another task, then there are n × m ways to do the two tasks in sequence.

For example:

If there are 5 different shirts and 3 different pairs of pants, then 
5 × 3 = 15 possible outfits, since each shirt can be worn with any pants.
Shirt: 5 Ways Pants: 3 Ways Total: 5 × 3 = 15 ways 15 Outfits

Permutation

Permutation deals with arranging a group of objects in a sequential manner. The number of permutations of n distinct objects is n! (n factorial), which is given as:

n! = n × (n-1) × (n-2) × ... × 2 × 1

Example: In how many ways can we arrange the letters A, B and C?

There are three things here, so let's calculate:
3! = 3 × 2 × 1 = 6 ways
ABC ACB BAC BCA Cab CBA Total = 6 ways

Permutations of subsets

While arranging the subsets of the whole set we use the following formula:

P(n, r) = n! / (n-r)!

Where n is the total number of items, and r is the number of items to arrange.

Example: In how many ways can we arrange 2 letters from the group {A, B, C}?

P(3, 2) = 3! / (3-2)! = 6 / 1 = 6 ways
Arrangement: AB, AC, BA, BC, CA, CB

Combination

Combinations represent the number of ways to select items from a set regardless of the order of selection. The formula for combinations is given as:

C(n, r) = n! / [r! × (n-r)!]

Example: In how many ways can we select 2 items from the set {A, B, C, D}?

C(4, 2) = 4! / (2! × (4-2)!) = 6 ways
Combination: AB, AC, AD, BC, BD, CD
Now AC Advertisement BC BD CD Total = 6 ways

Binomial theorem

The binomial theorem is a fundamental result that describes the algebraic expansion of the powers of a binomial expression. The theorem can be stated as follows:

(a + b)^n = Σ C(n, k) × a^(n-k) × b^k

Where Σ represents summation and k ranges from 0 to n . Here C(n, k) is the number of combinations and is represented as n choose k .

Example: Expand (x + y)^2 using the binomial theorem.

(x + y)^2 = c(2, 0) * x^2 * y^0 + c(2, 1) * x^1 * y^1 + c(2, 2) * x^0 * y^2
          = 1 * x^2 + 2 * xy + 1 * y^2
          = x^2 + 2xy + y^2

Pigeonhole principle

The Pigeonhole Principle is a simple but powerful idea that states that if you try to allocate more items than the number of containers, at least one container should contain more than one item.

Example: In a group of 13 people, at least two people must have been born in the same month, because there are only 12 months.

It is used to prove existence, but does not indicate method; for example, knowing two people have the same birthday without identifying them.

Conclusion

The world of combinatorics is vast and complex, involving far more than what can be briefly covered here. From generating functions to graph theory, pattern enumeration, and beyond, combinatorics employs a set of tools and concepts needed to tackle complex mathematical challenges. Each principle, formula, and theorem provides powerful insights and utility in diverse fields such as computer science, cryptography, and operations research.


Graduate → 10.2


U
username
0%
completed in Graduate

← Prev (10.1.4)
Network Flows
Next (10.2.1) →
Permutations and Combinations

Comments 



Combinatorics

https://www.buddymath.com/g/10.2?bmal=en