With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

2

Sieve Methods

2.1 Inclusion-Exclusion

Roughly speaking, a “sieve method” in enumerative combinatorics is a method for determining the cardinality of a set S that begins with a larger set and somehow subtracts off or cancels out unwanted elements. Sieve methods have two basic variations: (1) We can first approximate our answer with an overcount, and then subtract off an overcounted approximation of our original error, and so on, until after finitely many steps we have “converged” to the correct answer. This method is the combinatorial essence of the Principle of Inclusion-Exclusion, to which this section and the next four are devoted. (2) The elements of the larger set can be weighted in a natural combinatorial way so that the unwanted elements ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required