rag/knowledge_base/combinatorics.md

Combinatorics

Fundamental Counting Principle

If task 1 can be done in $m$ ways and task 2 in $n$ ways:

• Sequential (AND): $m \times n$ ways
• Choice (OR): $m + n$ ways

Permutations

• $n$ objects, arrange $r$: $P(n,r) = \frac{n!}{(n-r)!}$
• All $n$ objects: $n!$
• With repetition: $\frac{n!}{n_1! n_2! \cdots n_k!}$
• Circular permutation: $(n-1)!$

Combinations

• $\binom{n}{r} = \frac{n!}{r!(n-r)!}$
• $\binom{n}{r} = \binom{n}{n-r}$
• $\binom{n}{0} = \binom{n}{n} = 1$
• $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$ (Pascal's identity)

Inclusion-Exclusion Principle

$|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum|A_i| - \sum|A_i \cap A_j| + \sum|A_i \cap A_j \cap A_k| - \cdots$

Stars and Bars

• Non-negative integer solutions to $x_1 + x_2 + \cdots + x_r = n$: $\binom{n+r-1}{r-1}$
• Positive integer solutions: $\binom{n-1}{r-1}$

Derangements

Number of permutations with no fixed points: $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

JEE Tips

• "Arrange" → Permutation (order matters)
• "Select/Choose" → Combination (order doesn't matter)
• For identical objects, use combinations with repetition
• Distribution of identical objects into distinct boxes: Stars and Bars