Difference between revisions of "2008/09/09 MA375Fall2008walther" - Rhea

Revision as of 14:22, 9 September 2008

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} $