Contents
MA375: The Principle of Induction
Lecture Notes
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: Suppose there are 3 baskets with fruits(apples, oranges, pears), in how many ways can you choose a total of n fruits? ???
Answer:
Define: A: Apple O:Orange P:Pear $ B_1 ... B_n $ : Baskets
When n=0, only 1 way, no fruits on any basket.
When n=1, A in $ B_1 $, O in $ B_2 $, P in $ B_3 $
When n=3, AAA in $ B_1 $, AAO in $ B_2 $, AAP in $ B_3 $, AOO in $ B_4 $, AOP in $ B_5 $, APP in $ B_6 $, OOO in $ B_7 $, OOP in $ B_8 $, OPP in $ B_9 $, PPP in $ B_10 $
Use traingular numbers and we can figure that, each fruit basket we take have ____ to a monomial in 3 variables of degree n.
- PLEASE CONTINUE... ADD some more.. I'm a bit lost when copying this note... **
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} $
