6.042J/18.062J Staff Notes
Week of Tues., Mar. 29 through Monday, April 4

----------------------------------------------------------------------

Reading: 

----------------------------------------------------------------------

Lecture 14: Generating Functions

15    Ordinary generating functions
	Definition
	Examples

25    Solving recurrences with OGF's
	Running example: $a_0 = 0$, $a_n = 3a_{n-1}+2$
	Define sequence and OGF of seq.
	Multiply both sides by $x^n$ and sum over valid indices
	Express in terms of OGF
	Solve for OGF
	Solve for coeff of $x^n$ (using partial fractions)

25    OGF's for combinations
	OGF of binomial sequence
	$(1+x)^n$
	Theorem: product of OGF's for choosing from union of sets
	Convolution

15    Examples
	Count: ways of picking red and blue objects
	Count: ways to choose n objs from k types with repeated types
	Count: bags of fruit

----------------------------------------------------------------------

Lecture 15: More OGF's

15    Manipulating OGF's
	Shifting
	Linearity
	Even and odd terms
	Derivatives and integrals
	Products
	Multiply by $1/(1-x)$
	  justify
	  Ex: <1,2,3,4,...> has OGF $1/(1-x)^2$

15    Extended example
	What is OGF of $\sum_{k=0}^n k^2$?
	Find OFG of <0^2,1^2,2^2,3^2,...> ($= \frac{x+x^2}{(1-x)^3}$)
	Multiply by $1/(1-x)$
	Use binomial thm to find coeff $(1-x)^{-4}$
	Solve to get $n(n+1)(2n+1)/6$

15    Extended example
	Count: # ways to choose n objs from k types with inf. repetition
	Recall stars and bars
	Binomial theorem: find coeff of $x^n$ in $(1-x)^{-k}$
	New trick: Evaluate derivatives of OGF
	
30    Extended example
	Count: # of binary trees on n nodes
	Graphical def of binary tree
	Enumerate 5 binary trees on 3 nodes
	Recurrence
	OGF
	Convolution
	Lots of algebra
	Catalan numbers

[Class ran over by 10 minutes]

----------------------------------------------------------------------

Recitation: