6.042J/18.062J Staff Notes
Week of Tues., Mar. 8 through Monday, Mar. 14

No class on Tuesday, Mar. 8
Quiz 1 7-9pm on Wednesday, Mar. 9

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

Reading: M&R Sections 4.1-4.3, 4.10

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

Lecture 11: Pigeonhole principle, intro to counting theory

10    Pigeonhole principle
	Proof
	Ex. undirected graph has 2 vertices of same degree
	Ex. something simple

15    Strong pigeonhole principle
	Ex. at least one of a set of numbers must exceed average
	Ex. Label chessboard with 1 to 64

15    Rules of sum/product/division
	Rules of sum/product
	Ex. choosing textbooks
	Rule of division
	Ex. Handshaking lemma
	Ex. Number of palindromes

15    Permutations
	r-perms
	Formula for P(n,r)
	Ex. Number of ways can ring be formed = (n-1)!

15    Combinations
	r-combs
	Formula for C(n,r)
	Derivation from P(n,r)
	Ex. Choose 3 numbs from 1,2,...,10 so that sum is divisible by 3.

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

Recitation -- Friday, Mar. 11

Examples, examples, examples
Number of binary ``UPC'' codes (can't allow w and w^R if w\neq w^R)
[[What else did they do?  I forget.  CEL]]