Permutation & Combination — NDA Mathematics

Formulas (3)

• The fundamental principle of counting · Permutations, combinations, and their link
  $$^nP_r=\dfrac{n!}{(n-r)!} \qquad ^nC_r=\dfrac{n!}{r!\,(n-r)!} \qquad ^nP_r=\,^nC_r\cdot r!$$
• Factorials: divisibility and trailing zeros · Trailing zeros of n!
  $$Z(n!)=\left\lfloor\dfrac{n}{5}\right\rfloor+\left\lfloor\dfrac{n}{25}\right\rfloor+\left\lfloor\dfrac{n}{125}\right\rfloor+\cdots$$
• Binomial coefficient identities · Binomial coefficient identities
  $$^nC_r=\,^nC_{n-r} \qquad ^nC_r+\,^nC_{r-1}=\,^{n+1}C_r \qquad \sum_{r=0}^{n}{}^nC_r=2^n \qquad r\cdot{}^nC_r=n\cdot{}^{n-1}C_{r-1}$$

Watch out for (2)

• Permutation vs combination — does order matter?
  → The fundamental principle of counting
• $0!=1$, not $0$
  → Factorials: divisibility and trailing zeros

Watch out for (1)

• Repeated letters → divide by the repeat-factorials
  → Arranging objects (with repeats)

Watch out for (2)

• Use $^nC_r=\,^nC_{n-r}$ — and count the empty set
  → Selections and subsets
• 'At least one' = total − none (don't sum cases)
  → Constrained selection: at-least, at-most, cases

Formulas (1)

• Sum of all numbers formed · Sum of all numbers formed from n distinct digits
  $$\text{Sum}=(n-1)!\times(\text{sum of digits})\times\underbrace{111\ldots1}_{n\text{ ones}}$$

Formulas (1)

• Lines, triangles and polygons from points · Geometric counting from points and lines
  $$\text{lines}=\,^nC_2 \qquad \text{triangles}=\,^nC_3 \qquad \text{diagonals}=\dfrac{n(n-3)}{2} \qquad \text{parallelograms}=\,^mC_2\cdot{}^nC_2$$

Watch out for (1)

• Collinear points form no triangle — subtract $^kC_3$
  → Lines, triangles and polygons from points