Revision as of 07:10, 20 May 2013

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

Back to MA375, Fall 2008, Prof. Walther