← Number & Algebra
Mathematics · Cheatsheet

Number & Algebra

Chapter 3 · Counting

📋 Reference · always available
Multiplication principle (AND)
If task A has aa outcomes and task B has bb outcomes, doing both in sequence gives a×ba \times b outcomes. Generalises to any number of independent stages.
Addition principle (OR)
If task A has aa outcomes and task B has bb outcomes and they are mutually exclusive alternatives, choosing one or the other gives a+ba + b outcomes.
Factorial
n!=n(n−1)(n−2)⋯2⋅1,0!=1n! = n(n-1)(n-2)\cdots 2\cdot 1,\quad 0! = 1
Factorial — quick facts
1!=1,  2!=2,  3!=6,  4!=24,  5!=120,  6!=720,  7!=50401!=1,\;2!=2,\;3!=6,\;4!=24,\;5!=120,\;6!=720,\;7!=5040. Grows extremely fast — by 10!10! you are past 3.6 million.
Arrange all $n$ distinct objects in a row
n!n!
Number of orderings of nn different items along a line.
Permutation of $r$ from $n$ (order matters)
nPr=n!(n−r)!{}^{n}P_r = \frac{n!}{(n-r)!}
Pick rr items from nn AND arrange them. Example: 3-letter codes from 5 letters with no repeats =5P3=60= {}^5P_3 = 60.
Identical-objects formula
n!n1! n2!⋯nk!\frac{n!}{n_1!\,n_2!\cdots n_k!}
Arrange nn items where n1,n2,…n_1, n_2, \dots are repeats of each kind. Example: arrangements of MISSISSIPPI =11!1! 4! 4! 2!=34,650= \tfrac{11!}{1!\,4!\,4!\,2!} = 34{,}650.
Circular arrangement
(n−1)!(n-1)!
Round table: fix one person to remove rotational symmetry, then arrange the remaining n−1n-1 linearly.
Combination (order does not matter)
nCr=(nr)=n!r! (n−r)!{}^{n}C_r = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}
Pick rr items from nn when order is irrelevant. Equal to nPrr!\tfrac{{}^nP_r}{r!} — divide out the r!r! orderings of each chosen group.
Symmetry of $\binom{n}{r}$
(nr)=(nn−r)\binom{n}{r} = \binom{n}{n-r}
Choosing rr to include = choosing n−rn-r to leave out.
Quick values
(n0)=(nn)=1,  (n1)=(nn−1)=n,  (n2)=n(n−1)2\binom{n}{0}=\binom{n}{n}=1,\;\binom{n}{1}=\binom{n}{n-1}=n,\;\binom{n}{2}=\tfrac{n(n-1)}{2}
Pascal's rule
(nr)=(n−1r−1)+(n−1r)\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}
Each entry of Pascal's triangle is the sum of the two above it. Useful for shortcuts and proofs.
Binomial theorem
(a+b)n=∑r=0n(nr)an−rbr(a+b)^n = \sum_{r=0}^{n}\binom{n}{r}a^{n-r}b^{r}
Expands (a+b)n(a+b)^n into n+1n+1 terms: powers of aa fall from nn to 00, powers of bb rise from 00 to nn, coefficients come from row nn of Pascal's triangle.
General term
Tr+1=(nr)an−rbrT_{r+1} = \binom{n}{r}a^{n-r}b^{r}
The (r+1)(r+1)-th term, indexed from r=0r=0. Use this to extract a specific term (e.g. the x5x^5 term) without expanding the whole thing.
Coefficient extraction — recipe
To find the coefficient of xkx^k in (α+βx)n(\alpha + \beta x)^n: write Tr+1=(nr)αn−r(βx)rT_{r+1} = \binom{n}{r}\alpha^{n-r}(\beta x)^{r}, set the power of xx to kk, solve for rr, evaluate.
Pascal's triangle (first rows)
Row 0: 1 — Row 1: 1 1 — Row 2: 1 2 1 — Row 3: 1 3 3 1 — Row 4: 1 4 6 4 1 — Row 5: 1 5 10 10 5 1 — Row 6: 1 6 15 20 15 6 1.
Decision tree: P or C?
Ask: does the order of the chosen items change the outcome? YES ⇒ permutation (nPr)({}^nP_r). NO ⇒ combination (nCr)({}^nC_r). Seating, codes, ordered podiums ⇒ P. Committees, hands of cards, picking a team ⇒ C.
Decision tree: multiply or add?
AND between independent stages ⇒ multiply. OR between mutually exclusive cases ⇒ add. Split a mixed problem into disjoint cases first (add), then count each case (multiply).
Pitfall — double-counting
If swapping two identical items gives the same arrangement, you have over-counted. Divide by the symmetries (use the identical-objects formula or factor out the equivalent orderings).
Pitfall — wrong power in binomial
In (a+bx)n(a + bx)^n, every term carries an extra power of bb as well as xx. Do not drop the brb^r. In (a−bx)n(a - bx)^n, term rr carries (−1)r(-1)^r.
Pitfall — calculator
nPr{}^nP_r and nCr{}^nC_r have dedicated GDC buttons (often under MATH → PRB). Do not compute n!/(n−r)!n!/(n-r)! for large nn — overflow risk. Use the built-in function.