Contents
The Overall Picture
Theorem: The following are equal:
- The number of ways to pick n fruits from r types of fruit
- The number of monomials in r variables of degree n
- The number of arragnements of n "*"'s and r-1 "|"'s
- $ {n+r-1 \choose r-1} $
- The number of solutions to the equation $ x_1 + x_2 + \dots + x_r = n,\text{ where }x_i \in \mathbb{N} $
Choosing n fruits from r baskets
Example: ???
Stars and Bars
Example: ???
Kids and Chocolate
Example: ???
Driving Directions
Example: Suppose we are in a city where a rectangular grid of streets looks as follows:
_ _ _ _ _. <- Destination
/\ |_|_|_|_|_|
|| |_|_|_|_|_|
North |_|_|_|_|_|
|_|_|_|_|_|
You-> `
You start in the southwest corner, and want to get to the Northeast corner. How many optimal routes could you take?
Solution: An optimal route would consist of the least number of streets one must travel. In other words, one should only go north or east on roads, never south or west. No matter which optimal path we take, then, we will end up traveling north 4 times and east 5 times.
Consider encoding this route. For example, NNEEENNEE would mean, "Go north 2 blocks, then east 3 blocks, then north 2 blocks, then east 2 blocks." Since there will always be only norths and easts, we really only have to know where the norths are, and we can then fill in the easts. Thus, all we need to do is pick four spaces out of the nine possible to fill in the norths (e.g., _ _ _ _ _ _ _ _ _ -> N N _ _ _ N N _ _). How many ways can this be done?
$ {9 \choose 4} $
