Formula sheet · Modern Math - Permutation & Combination

Permutation & Combination Formula Sheet

All QA formula sheets

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

FormulaWhen to use
Multiplication rule: \(m \times n\) ways; addition rule: \(m + n\) waysMultiply 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

FormulaWhen 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

FormulaWhen 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.

Practise Modern Math - Permutation & Combination →