✅ UNIT 2 — COMBINATORICS (DISCRETE MATHEMATICS)

 

✅ UNIT 2 — COMBINATORICS

1. Permutations & Combinations

Permutation

Arrangement of objects where order matters.

• Formula:

  $$^nP_r = \frac{n!}{(n-r)!}$$

Example:
Number of ways to arrange 3 letters from ABCD
= $^4P_3 = 24$

Combination

Selection of objects where order does NOT matter.

• Formula:

  $$^nC_r = \frac{n!}{r!(n-r)!}$$

Example:
Choose 2 students from 5
= $^5C_2 = 10$

---

2. Summation

Properties of Σ:

• Linearity:
  $\sum (a_i + b_i) = \sum a_i + \sum b_i$

• Constant factor:
  $\sum c\cdot a_i = c\sum a_i$

---

3. Binomial Function

Binomial Theorem:

$$(a + b)^n = \sum_{k=0}^{n} {^nC_k a^{n-k} b^k}$$

Properties:

• Number of terms = n+1

• Middle term depends on n (odd/even)

• Coefficients symmetric:

  $$^nC_k = ^nC_{n-k}$$

---

4. Generating Functions

Used in recurrence and combinatorics.

Basic idea:

If we have sequence {a₀, a₁, a₂, …}
Generating function is:

$$G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$$

Example: For sequence 1,1,1,1,…

$$G(x) = \frac{1}{1 - x}$$

---

5. Recurrence Relation

Example: Fibonacci

$$f(n) = f(n-1) + f(n-2)$$

Solving Linear Recurrences

General form:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2}$$

Steps:

1. Form characteristic equation

   $$r^2 - c_1 r - c_2 = 0$$

2. Find roots r₁, r₂

3. General solution:

   $$a_n = A r_1^n + B r_2^n$$