Permutations and Combinations

Counting basics

Permutations and combinations
$^{n} P_{r} = \frac{n !}{( n - r )!},$ $^{n} C_{r} = \frac{n !}{r ! ( n - r )!}$
Properties
$^{n} C_{r} =^{n} C_{n - r},$ $^{n} C_{r} +^{n} C_{r - 1} =^{n + 1} C_{r},$ $r^{n} C_{r} = n^{n - 1} C_{r - 1}$
With repetition
arrangements of $r$ from $n$ with repetition $= n^{r}$
Identical objects
$\frac{n !}{p ! q ! r ! \dots}$ (p alike, q alike, …)

$(n - 1)!$ ways $;$ $\frac{( n - 1 )!}{2}$ if clockwise and anticlockwise are the same (necklace)

Total selections
$^{n} C_{0} +^{n} C_{1} + \dots +^{n} C_{n} = 2^{n};$ at least one: $2^{n} - 1$
Alike objects
$(p + 1) (q + 1) (r + 1) - 1$ selections from p, q, r alike objects (at least one)
n identical into r groups
$^{n + r - 1} C_{r - 1}$ (empty allowed) $,$ $^{n - 1} C_{r - 1}$ (none empty)
Non-negative integer solutions
$x_{1} + x_{2} + \dots + x_{r} = n :^{n + r - 1} C_{r - 1}$
Distinct into groups
$\frac{( m + n )!}{m ! n !} (m \neq = n);$ $\frac{( 2 n )!}{2 ! ( n ! ) ^{2}}$ (two equal groups)
Number of divisors
$N = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots : (a_{1} + 1) (a_{2} + 1) \dots$ divisors

$D_{n} = n! (1 - \frac{1}{1 !} + \frac{1}{2 !} - \frac{1}{3 !} + \dots + \frac{( - 1 ) ^{n}}{n !})$
$D_{1} = 0, D_{2} = 1, D_{3} = 2, D_{4} = 9, D_{5} = 44$ .