18.1 Basic counting principles

18.1.1 Finding the number of permutations

How many ways can we arrange distinct people in a straight line? For $n$ people in a straight line, we can put $n$ people in the first position, $n-1$ people in the second position, $n-2$ in the third, and so on. Overall, then the number of ways of arranging distinct people in a line is equal to

(n)(n-1)(n-2)...1=n!

(18.1)

TODO

18.1.2 From English to maths

One thing that can be tricky in combinatorics is working out what words in English mean in terms of combinatorial operations. Here’s a handy dictionary.

English	Combinatorics
This can happen in way $A$ or in way $B$	number of ways for $A$ + number of ways for $B$
To have "whatever" I need both $A$ and then $B$	number of ways of $A$ $\times$ number of ways $B$
For every item in this set of $n$ objects there are $k$ ways of obtaining it.	$k^{n}$
I have a group of $n$ things, and I want to pick $k$ of them, but I don’t care about the order in which I get them.	$\binom{n}{k}$
I have a group of $n$ different things, and I want to pick $k$ of them, and I do care about the order in which I get them	$\frac{n!}{(n-k)!}$

One strategy I find very useful in solving combinatorics problems is to write out a description of what I’m after in English, and then translate this into combinatorial operations (e.g. permutations, combinations, etc.). ¹¹ 1 This strategy works really well throughout mathematics, but it’s especially helpful here.