Combinations & Permutations

Permutations without Repetition

Permutations without repetition $\large r$ $\large n$ elements such that there are no repetitions.

^{n} P_{r} = \frac{n!}{(n - r)!}

There are 12, 3-letter words that can be generated from the letters of the word FART:

FA, AF, FR, RF, FT, TF, AR, RA, AT, TA, RT, TR

^{4} P_{2} = \frac{4!}{(4 - 2)!} = 12

Permutations with repetition $\large r$ $\large n$ elements such that there may be repetitions.

n^{r}

There are 8 possible arrangements of 1s and 0s in a 3-digit binary number:

000, 001, 010, 011, 100, 101, 110, 111.

2^{3} = 8

Combinations without repetition $\large r$ $\large n$ elements such that there are no repetitions.

^{n} C_{r} = (\binom{n}{r}) = \frac{n!}{r! (n - r)!}

There are 4, 3-letter combinations that can be generated from the letters of the word FART:

FAR, FRT, FAT, ART.

^{4} C_{3} = \frac{4!}{3! (4 - 3)!} = 4

\begin{matrix} (\binom{n}{r}) = (\binom{n - 1}{r - 1}) + (\binom{n - 1}{r}) \\ (\binom{n}{r}) = (\binom{n}{n - r}) \end{matrix}

Combinations with repetition $\large r$ $\large n$ elements such that there may be repetitions.

((\binom{n}{r})) = (\binom{n + r - 1}{r}) = \frac{(n + r - 1)!}{r! (n - 1)!}

There are 10 ways to place 2 balls into 4 different boxes:

4 ways where both balls are in the same box, 6 other ways to choose 2 different boxes from 4.

((\binom{4}{2})) = \frac{5!}{2! 3!} = 10

Binomial theorem $\large (x + y)^n$ .

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k}

Multinomial coefficients $\large n$ $\large r$ $\large n_1, n_2, n_3, ..., n_r$ $\large \sum\limits^r_{k = 1} n_k = n$ .

(\binom{n}{n_{1}, n_{2}, n_{3}, . . ., n_{r}}) = \frac{n!}{n_{1}! n_{2}! n_{3}! . . . n_{r}!}

Multinomial theorem $\large (x_1 + x_2 + x_3 + ... + x_r)^n$ .

(x_{1} + x_{2} + x_{3} + . . . + x_{r})^{n} = \sum_{n_{1} + n_{2} + . . . + n_{r} = n} (\binom{n}{n_{1}, n_{2}, n_{3}, . . ., n_{r}}) \prod_{k = 1}^{r} x_{k}^{n_{k}}