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