Permutations & Combinations – Rapid Review

Fundamental Principle of Counting

• Rule of Sum: if a task can be done in $m$ ways or $n$ ways (exclusive), total $m+n$.

• Rule of Product: if Stage-1 has $m$ outcomes and Stage-2 (following it) has $n$, total $m\,n$.

Factorial Basics

• $n! = n(n-1)\dots1$ ; $0! = 1$.

• Recursive: $n! = n\,(n-1)!$.

Permutations

• Distinct objects, order matters: $^nP_r = \dfrac{n!}{(n-r)!}$.

• All $n$ objects: $n!$.

• Repetition allowed: $n^r$.

• With identical items: $\dfrac{n!}{p!q!r!\dots}$ (where groups have $p,q,r\dots$ alike).

• “Always together” (string method): if $m$ specified stick together inside $n$ total ⇒ $m!\,(n-m+1)!$.

Combinations

• Order irrelevant: $^nC_r = \dfrac{n!}{r!(n-r)!}$.

• Key identities: $^nC<em>r = ^nC</em>{n-r}$ ; $^nC<em>0+^nC</em>1+\dots+^nC<em>n = 2^n$ ; biggest term is $^nC</em>{\lfloor n/2\rfloor}$.

• Restrictions:
  • Exclude $p$ fixed objects ⇒ $(n-p)C<em>r$. • Include $p$ fixed objects ⇒ $(n-p)C</em>{r-p}$.

• Identical items: choosing any number from $k$ identical objects gives $k+1$ ways.

Division into Groups

• Split $m+n$ distinct items into two unequal groups: $\dfrac{(m+n)!}{m!\,n!}$.

• Two equal groups of $n$ each: $\dfrac{(2n)!}{n!\,n!\,2!}$.

• $(m+n+p)$ into three unequal: $\dfrac{(m+n+p)!}{m!\,n!\,p!}$; equal $n$ each ⇒ $\dfrac{(3n)!}{(n!)^3\,3!}$.

• Into $m$ equal unlabeled boxes, $mn$ distinct items: $\dfrac{(mn)!}{(n!)^m\,m!}$ (multiply by $m!$ if boxes labeled).

Circular Arrangements

• $n$ distinct objects around a table: $(n-1)!$ (clockwise ≠ anticlockwise).

• If a necklace/garland (mirror same) ⇒ $\tfrac12(n-1)!$.

• $r$ of $n$ around a circle: $\dfrac{^nP<em>r}{r}$ (or $\dfrac{^nP</em>r}{2r}$ if reflections identical).

Non-Negative/Positive Integer Solutions

For $x<em>1+\dots+x</em>k=n$:

• Non-negative: $\displaystyle {n+k-1\choose k-1}$.

• Positive: $\displaystyle {n-1\choose k-1}$.

Derangements (nothing in own place)

• Number with $n$ items: $D_n = n!\left(1-\frac1{1!}+\frac1{2!}-\dots+(-1)^n\frac1{n!}\right)\approx \dfrac{n!}{e}$.

Inclusion–Exclusion (two sets version)

$|A\cup B| = |A|+|B|-|A\cap B|$.
General: alternately add/subtract intersections of increasing size.

Linear (Unit-Coefficient) Equations

Distributing $n$ identical objects to $r$ persons (none can be <0): same formula as non-negative solutions.

Prime-Exponent in $n!$ (Legendre)

$e<em>p(n!) = \displaystyle \sum</em>{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$.

Divisors of an Integer

If $N=p^a q^b r^c\dots$ then:

• Number of divisors: $(a+1)(b+1)(c+1)\dots$.

• Sum of divisors: $(1+p+\dots+p^a)(1+q+\dots+q^b)\dots$.

• Pairs of factors: half this count (adjust for perfect square).

• Coprime factor-pairs: $2^{k-1}$ where $k$ is number of distinct primes.

Useful Digit/Divisibility Checks (4-digit examples)

Even ⇒ last digit even; divisible by $3$ ⇒ digit-sum multiple of $3$; by $6$ ⇒ even and digit-sum multiple of $3$, etc.

Quick Sum Formulas for All Numbers with Given Digits

Using digits $a<em>1\dots a</em>n$ (distinct):

• Each digit appears $(n-1)!$ times in each place.

• Sum of all numbers length $n$: $(a<em>1+\dots+a</em>n)(n-1)!\,(111\dots 1_{(n\text{ times})})$.

Multinomial Coefficient

Number of ways to put $r$ labeled items into boxes of sizes $l,m,n,\dots$ equals coefficient of $x^r$ in $\prod (1+x+\dots+x^{\text{size}})$.

Standard Shortcuts

• No two selected objects adjacent in a line of $N$ ⇒ choose gaps: $\displaystyle {N-n+1\choose n}$ (multiply by $n!$ if persons distinct).

• Arrange $m$ W-balls and $n$ R-balls so that no two Rs touch (distinct balls): $\displaystyle {m+1\choose n} m! n!$ (omit factorials for identical sets).

These formulas cover almost every “last-minute” question on counting, permutations–combinations, circular arrangements, distributions, and factorial exponents.