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

📊Visual Mathematical Intuition

Combinatorial Grid Lattice Paths & Pascal's Triangle Symmetry

Lattice Path Formula:

\text{Paths}(0,0) \to (m, n) = \binom{m+n}{m} = \frac{(m+n)!}{m! n!}

Pascal Recurrence:

\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}

Symmetry Property:

\binom{n}{r} = \binom{n}{n-r}

Combinatorial 2D lattice paths from $(0,0)$ to $(m,n)$ equaling $\binom{m+n}{m}$ , connected with Pascal's triangle recurrence and horizontal reflection symmetry.

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! [1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(- 1)^{n}}{n!}] = [\frac{n!}{e}]

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 ​

Permutations & Combinations ​

Partitioning & Distribution (Stars & Bars Method) ​

2. Derangements & Inclusion-Exclusion Principle ​

3. Binomial Theorem & Coefficient Identities ​

Key Binomial Coefficient Identities ​

4. Multinomial Theorem ​