Inclusion-exclusion principle

For finite sets $A_1,\dots ,A_n$, the cardinality of their union is the alternating sum of the cardinalities of their nonempty intersections.

Let $f$ take values in the additive cyclic group $\mathbb{Z}/n\mathbb{Z}$ on a cycle with $n$ vertices. A constraint on edge $j$ prescribes $f(j)-f(j-1)=c_j$. Any proper selection of $k<n$ edges leaves disjoint paths, hence $n-k$ free initial values and $n^{n-k}$ solutions. The full cycle has $n$ solutions if ${\sum }_j{c}_j=0$ and none otherwise. Combining these intersection counts with the inclusion-exclusion principle giveswhere $F$ is $n$ or zero according to the full-cycle consistency condition. This is a useful example in which every proper collection of local constraints is independent, but the full collection has one global obstruction.

Truncating the inclusion-exclusion principle after an odd number of terms gives an upper bound, and truncating after an even number gives a lower bound. In particular,