Improved bounds on the probability of a union and on the number of events that occur

Let be events in a sample space. Given the probability of the intersection of each collection of up to 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.