Permutation & Combination Formula Sheet
Permutation and Combination is a regular source of CAT questions, often as TITA. Decide first whether order matters and whether the objects and the boxes are identical or distinct; the right formula follows from those two answers.
Core counting
| Formula | When to use |
|---|---|
| Multiplication rule: \(m \times n\) ways; addition rule: \(m + n\) ways | Multiply for steps done one after another ("and"); add for separate cases ("or"). |
| \(n! = n \times (n - 1) \times \dots \times 1\), with \(0! = 1\) | Arranging all \(n\) distinct objects in a row. |
| \({}^nP_r = \dfrac{n!}{(n - r)!}\) | Arranging \(r\) out of \(n\) distinct objects, order matters, \(0 \le r \le n\). |
| \({}^nC_r = \binom{n}{r} = \dfrac{n!}{r!\,(n - r)!}\) | Selecting \(r\) out of \(n\) distinct objects, order does not matter, \(0 \le r \le n\). |
| \(\binom{n}{r} = \binom{n}{n - r}\); \(\binom{n}{r} + \binom{n}{r - 1} = \binom{n + 1}{r}\) | Simplifying selections, for \(1 \le r \le n\). |
| \(\dfrac{n!}{p!\,q!\,r!\cdots}\) | Arranging \(n\) objects in a row where \(p\) are alike of one kind, \(q\) of another, and so on (letters of a word). |
| \(n^r\) | Arrangements of length \(r\) from \(n\) distinct objects when repetition is allowed. |
Arrangements and selections
| Formula | When to use |
|---|---|
| Circular arrangements \(= (n - 1)!\) | \(n\) distinct people around a round table, where only relative positions matter. |
| Necklace or garland \(= \dfrac{(n - 1)!}{2}\) | \(n \ge 3\) distinct beads, when clockwise and anticlockwise orders count as the same. |
| \(2^n - 1\) | Selecting at least one object from \(n\) distinct objects. |
| \((p + 1)(q + 1)(r + 1) - 1\) | Selecting at least one object from \(p\) identical, \(q\) identical and \(r\) identical objects of different kinds. |
| Handshakes or lines \(= \binom{n}{2}\); triangles \(= \binom{n}{3}\); polygon diagonals \(= \binom{n}{2} - n\) | \(n\) people or \(n\) points with no three collinear. |
| Grid paths \(= \binom{m + n}{m}\) | Shortest paths on a grid moving only right or up, \(m\) steps right and \(n\) steps up. |
| Derangements \(D_n = n!\left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dots + \dfrac{(-1)^n}{n!}\right)\); \(D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44\) | Ways to put \(n\) letters in \(n\) envelopes so that none is in its correct envelope. |
Distribution
| Formula | When to use |
|---|---|
| \(\binom{n + r - 1}{r - 1}\) | \(n\) identical objects into \(r\) distinct boxes, empty boxes allowed. Same as non-negative integer solutions of \(x_1 + \dots + x_r = n\). |
| \(\binom{n - 1}{r - 1}\) | \(n\) identical objects into \(r\) distinct boxes, each box non-empty (\(n \ge r\)). Same as positive integer solutions of \(x_1 + \dots + x_r = n\). |
| \(r^n\) | \(n\) distinct objects into \(r\) distinct boxes, any box may be empty (each object picks a box). |
| \(\dfrac{(mn)!}{(n!)^m \, m!}\) | Splitting \(mn\) distinct objects into \(m\) unlabelled groups of \(n\) each. Drop the \(m!\) if the groups are labelled. |
Shortcuts and traps
- Order or not: "arrange", "rank", "form numbers" means permutations; "choose", "select", "form a team" means combinations.
- Together: tie the objects that must be together into one unit, arrange the units, then multiply by the arrangements inside the unit.
- Never together: arrange the other objects first, then place the restricted ones in the gaps between them (gap method).
- At least one: count the total and subtract the cases with none, instead of adding many cases.
- Lower limits: for \(x_i \ge k\), substitute \(y_i = x_i - k\) to get a non-negative problem, then use \(\binom{n + r - 1}{r - 1}\) on the new total.