Counting — Permutations and Combinations

Almost every probability question on equally likely outcomes reduces to counting: $P(E) = |E| / |S|$. GATE uses counting both directly (NAT questions asking "how many ways") and inside probability problems (cards, balls in urns, committees, arrangements).

The two basic rules

• Sum rule. If a task can be done in one of $m$ ways or one of $n$ ways, with no overlap, it can be done in $m + n$ ways.
• Product rule. If a task is a sequence of two steps with $m$ choices for the first and $n$ for the second (for each first choice), it can be done in $m \cdot n$ ways.

Permutations — ordered selections

Why circular is $(n-1)!$: each circular seating corresponds to exactly $n$ linear seatings (its rotations), so $n!/n$.

Restrictions

• "Together": glue the items into one block, arrange the blocks, then multiply by the internal arrangements of the block.
• "Not together": total minus "together", or use the gap method — arrange the other items first, then choose gaps for the separated ones.

Combinations — unordered selections

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

Key properties:

• $\binom{n}{r} = \binom{n}{n-r}$ (choosing who's in = choosing who's out).
• Pascal's rule: $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ (either a particular item is chosen or not).
• $\sum_{r=0}^n \binom{n}{r} = 2^n$ — the number of subsets of an $n$-set.
• Vandermonde: $\binom{m+n}{r} = \sum_k \binom{m}{k}\binom{n}{r-k}$.

Distributing objects into boxes

Stars and bars

The non-negative integer solutions of $x_1 + \dots + x_k = n$ correspond to arrangements of $n$ stars and $k-1$ bars: $\binom{n+k-1}{k-1}$.

• Lower bounds $x_i \ge a_i$: substitute $y_i = x_i - a_i$ and reduce $n$.
• Upper bounds $x_i \le b_i$: use inclusion–exclusion on the violated bounds.

Binomial and multinomial theorems

$$(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}, \qquad (x_1 + \dots + x_m)^n = \sum_{k_1+\dots+k_m=n} \frac{n!}{k_1!\cdots k_m!}\, x_1^{k_1}\cdots x_m^{k_m}.$$

Useful consequences: $\sum_k (-1)^k \binom{n}{k} = 0$, $\sum_k k\binom{n}{k} = n2^{n-1}$, $\sum_k \binom{n}{k}^2 = \binom{2n}{n}$.

Inclusion–exclusion

$$|A_1 \cup \dots \cup A_n| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i\cap A_j\cap A_k| - \dots + (-1)^{n+1}|A_1\cap\dots\cap A_n|.$$

Use it whenever the question says "at least one", "none of", or "not divisible by any of".

Derangements

Permutations of $n$ items with no item in its original position:

$$D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}, \qquad 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, D_6 = 265$. The probability that a random permutation is a derangement tends to $1/e \approx 0.3679$.

The pigeonhole principle

If $N$ objects go into $k$ boxes, some box holds at least $\lceil N/k \rceil$ objects. It answers "minimum number needed to guarantee…" questions.

Counting in probability problems

Selecting with and without replacement

Quick revision