Counting

Counting is about finding how many ways a task can be done without listing every possibility. If one task can be done in $m$ ways and a second independent task in $n$ ways, doing both gives $mimesn$ total ways. Choosing $k$ items from $n$ distinct items, where order does not matter, uses combinations: inom{n}{k} = rac{n!}{k!(n-k)!}. A set with $n$ elements has $2^n$ subsets, since each element is either included or excluded. For paths moving only right or up, every shortest path contains a fixed number of right moves and up moves; count them by choosing which steps go in one direction.