6.042J Study Guide - Final Guide: Prilocaine, Handshaking, Nsb El 3
22 May 2016
School
Course
Professor
Document Summary
* f(n) = o(g(n)) c, n no, f(n) c*g(n) (at some n and c they"re equal) If function from a to b is k-to-1, then |a| = k|b|. k-to-1 exactly k elements hit each b element (k arrows into each b element) **be careful with double counting, triple with tuples etc. Multinomial coefficient: n choose m as, o bs: = Pigeonhole principle: if there are more pigeons than pigeonholes, two pigeons need to be in the same hole. If i have n pigeons and h holes, then some hole has pigeons. Inclusion/exclusion: |a u b| = |a| + |b| - |a. General: sum( (-1)|s|+1 | a i|) sum over s c {1,2,3, ,n} (x+y)n = sum ( xk yn-k ) over all ks (x1 + x2 + xk)n = sum ( x1 m2 xk m1 x2. Pr(u ei) sum(pr(ei)) (if disjoint events then =) Counting in probability: # outcomes in event / total # outcomes.
