Improved Bounds on the Probability of a Union and on the Number of Events that Occur

Let $A_1, A_2, \ldots, A_n$ be events in a sample space. Given the probability of the intersection of each collection of up to $k+1$ of these events, what can we say about the probability that at least $r$ of the events occur? This question dates back to Boole in the 19th century, and it is well known that the odd partial sums of the Inclusion- Exclusion formula provide upper bounds, while the even partial sums provide lower bounds. We give a combinatorial characterization of the error in these bounds and use it to derive a very simple proof of the strongest possible bounds of a certain form, as well as a couple of improved bounds. The new bounds use more information than the classical Bonferroni-type inequalities, and are often sharper.