Permutations, Combinations & Binomial Theorem

Combinatorial Principles

Combinatorics deals with counting, arrangement, and structural grouping. In high-level competitions, problems combine the Principle of Inclusion-Exclusion (PIE), Multinomial coefficients, Derangements, and Binomial series differentiation/integration.

1. Fundamental Principles & Counting Formulas

Permutations & Combinations

Permutation of $n$ distinct items taken $r$ at a time: $^{n} P_{r} = \frac{n!}{(n - r)!}$
Combination of $n$ distinct items taken $r$ at a time: $^{n} C_{r} = (\binom{n}{r}) = \frac{n!}{r! (n - r)!}$

Partitioning & Distribution (Stars & Bars Method)

Number of non-negative integer solutions to $x_{1} + x_{2} + \dots + x_{r} = n$ ( $x_{i} \geq 0$ ):

Solutions = (\binom{n + r - 1}{r - 1})

Number of strictly positive integer solutions ( $x_{i} \geq 1$ ):

Solutions = (\binom{n - 1}{r - 1})

2. Derangements & Inclusion-Exclusion Principle

Derangement Formula $D_n$

The number of permutations of $n$ distinct items such that no item appears in its original position is: $$D_n = n! \left[ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right] = \left[ \frac{n!}{e} \right]$$ Recurrence Relation: $D_n = (n - 1)(D_{n-1} + D_{n-2})$ with $D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44$.

3. Binomial Theorem & Coefficient Identities

(x + y)^{n} = \sum_{r = 0}^{n} (\binom{n}{r}) x^{n - r} y^{r}

Key Binomial Coefficient Identities

$\sum_{r = 0}^{n} (\binom{n}{r}) = 2^{n}$
$\sum_{r = 0}^{n} (- 1)^{r} (\binom{n}{r}) = 0 ⟹ C_{0} + C_{2} + C_{4} + \dots = C_{1} + C_{3} + C_{5} + \dots = 2^{n - 1}$
Pascal's Identity: $(\binom{n}{r}) + (\binom{n}{r - 1}) = (\binom{n + 1}{r})$
Vandermonde's Convolution Identity: $\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k}) = (\binom{m + n}{r})$
Sum of Squares: $\sum_{r = 0}^{n} {(\binom{n}{r})}^{2} = (\binom{2 n}{n})$

4. Multinomial Theorem

(x_{1} + x_{2} + \dots + x_{k})^{n} = \sum_{r_{1} + r_{2} + \dots + r_{k} = n} \frac{n!}{r_{1}! r_{2}! \dots r_{k}!} x_{1}^{r_{1}} x_{2}^{r_{2}} \dots x_{k}^{r_{k}}

Total Number of Terms in Expansion: $(\binom{n + k - 1}{k - 1})$

Permutations, Combinations & Binomial Theorem ​

1. Fundamental Principles & Counting Formulas ​