n balls into n bins: Pr[bin-1has≥t balls Pr a set S of t balls s.t.all balls in S are in bin-1 1 t n union bound ∑ Prall balls in S are in bin-1 set s of t balls (g）=-山<日≤ t!nt Stirling approximationn balls into n bins: union bound Stirling approximation Pr[ bin-1 has ￾ t balls ] ￾n t ￾ ￾ Pr [￾ a set S of t balls s.t. all balls in S are in bin-1 ] ￾ ￾ set S of t balls Pr[all balls in S are in bin-1] 1 nt ￾ 1 nt ￾n t ￾ = n(n ￾ 1)(n ￾ 2)···(n ￾ t + 1) t!nt ￾ 1 t! ￾ ￾e t ￾t