Combinatorics
Combinatorics is the study of counting, arrangement, and combination of objects.
1. Fundamental Counting Principle
If one event can occur in m ways, and another independent event can occur in n ways, then the
two events can occur together in m × n ways.
2. Permutations
A permutation is an arrangement of objects where order matters.
- Without repetition: P(n,r) = n!/(n-r)!
- With repetition: n^r
3. Combinations
A combination is a selection of objects where order doesn't matter.
C(n,r) = n! / (r!(n-r)!)
4. Binomial Theorem
(x + y)^n = Σ(k=0 to n) C(n,k) x^(n-k) y^k
5. Inclusion-Exclusion Principle
For sets A and B:
|A ∪ B| = |A| + |B| - |A ∩ B|
This principle extends to more than two sets.
6. Pigeonhole Principle
If n+1 items are put into n containers, then at least one container must contain more than one
item.
7. Recurrence Relations
A recurrence relation defines a sequence where each term is a function of previous terms.
Example: Fibonacci sequence
F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1
Solving recurrence relations:
- Substitution method
- Characteristic equation method
Combinatorics is essential in probability theory, algorithm analysis, and many areas of computer
science.
These documents cover key areas of discrete mathematics. Each topic is interconnected and
forms the foundation for advanced concepts in computer science and mathematics.
