6.042J/18.062J Staff Notes
Week of Tues., Mar. 15 through Monday, Mar. 21

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

Reading: M&R Sections 4.4-4.8.

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

Lecture 12: More counting

15    Binomial coefficients
	Definition
	$\choose{n}{k} = \choose{n}{n-k}$
	  algebraic and combinatorial proofs.
        Pascal's formula
	  Comb. proof.

20    Permutations of multisets
	Definition
	Repetition counts
	Count: r-perms of k-object multiset with infinite rep counts
	Count: r-perm of k-object multiset with finite rep counts
	Ex: perms of letters in MASSACHUSETTS

30    Combinations of multisets
	Definition
	Count: r-combs of n-object multiset with inf rep counts
	Stars and bars
	Ex: mono increasing 7-sequences of {1,2,...,10}
	Count: r-combs of n-object multiset with inf rep counts and
	  each object appears at least once

15    Extended example
	How many ways can the 2n+1 seats in a congress be divided among
	  3 parties so that any 2 parties can form a majority.
	Same, but 2n seats

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

Lecture 13: Binomial theorem and inclusion/exclusion

10    Binomial theorem
	Statement
	Ex: $(x+y)^4$
	Pascal's triangle
	Combinatorial proof of binomial theorem

10    Identities
	$\sum_{k=0}^n \choose{n}{k} = 2^n$
	$\sum_{k=0}^n (-1)^k\choose{n}{k} = 0$
	$\sum_{k=0}^{\floor{n/2} \choose{n}{2k} = 2^{n-1}$	
	$\sum_{k=0}^n k \choose{n}{k} = n2^{n-1}$

15    General binomial theorem
	Def of general binomial coefficient
	Statement of theorem (proof: advanced calculus)
	Ex: approximate $\sqrt{2}$

10    Multinomial theorem
	Statement
	Comb. proof

[Did not do:
10    Unimodality of binomial coeffs
	Ratio of successive terms
	Maximum at halfway point
]

10    Motivation for incl./excl.
	How many numbers from {1,...,100} are divisible by 3 or 5?
	Venn diagrams for 2 sets, then 3 sets

10    Incl/excl.
	General formula for size of union of sets
	General formula for size of intersection of set complements

15    Extended example
	How many 10-combs of {3\cdot a, 4\cdot b, 5\cdot c}?

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

Recitation -- Friday, Mar. 11

Examples, examples, examples
Number of binary ``UPC'' codes (can't allow w and w^R if w\neq w^R)