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.). 11 1 This strategy works really well throughout mathematics, but it’s especially helpful here.