Combinatorics, Week 3
February 8, 2017
The following outline was prepared by this week’s presenters,
Justin and Anuke.
Bars and stars [40m]
- We start with a descriptive problem: how many different ways can you fill a box of three with 1 type of bagel, how about 2 types, 3, 4?
- What changes? Do we see a pattern? Similar to word problems from first lecture!
- Generalize how to divide indistinguishable “bagels” over distinguishable categories
- How about a problem like (x+y+z)10
- Generalize for d degrees over k number of variables
- Walk through solving stars and bars problems with “cookies and kids” method / mindset
Random walk (lattice problem) [40m]
- How many ways to get through city with only Up and Right movements?
- Similar to word problem!
- Introduce forbidden square, now what?
- Relation to inclusion-exclusion formula
- What about with two forbidden squares?
- If there’s time, show connection between random walk and Pascal’s triangle
Tying together stars and bars with inclusion-exclusion [40m]
- How many monomials of degree 8 not divisible by xy3 or x3y?
- Brute force counting
- Adjusting for over counting (inclusion-exclusion equation)
- Generalizing: how could we count number of monomials of degree d? (bars and stars review)
- Diagram representation of problem, diagonal represents monomials of same degrees
- Visualize intersection // how inclusion-exclusion applies
- Generalize formula to account for all monomials of degree d not divisible by xy3 or x3y
The same books and sections as last week are helpful preparation for these topics.
See also the following Wikipedia articles: