Generalization of principle of inclusion and exclusion (PIE)

536 Views Asked by At

The PIE can be stated as $$|\cup_{i=1}^n Y_i| = \sum_{J\subset[n], J\neq \emptyset} (-1)^{|J|-1} |Y_J|$$ where $[n]=\{1,2,...,n\}$ and $Y_J=\cap_{i \in J} Y_i$.

Problems using it are usually reduced to counting problems and require finding a good union decomposition of the set you want to count. I would like to know if you have some applications of finding bounds on arbitrary integer sums or even evaluating them using setdecomposition and manipulation. The more vague question if the IEP can be generalized away from counting, for example some polynomial is certainly defined for integers so it sort of falls into the first question, but the real numbers are certainly not countable but maybe there is some connection.

references are appreciated, too.

1

There are 1 best solutions below

0
On BEST ANSWER

The principle of inclusion and exclusion is intimately related to Möbius inversion, which can be generalized to posets. I'd start digging in this general area.