# A Generalized version of Inclusion-Exclusion Principle?

I recently read Doron Zeilberger’s paper on Inclusion-Exclusion Principle.

Let’s say there are $n$ properties which are numbered $1,\cdots,n$.
And let $A$ be a set of elements which has some of these properties.
Then the Inclusion-Exclusion Principle states that the number of elements with no properties at all is
\begin{equation*}
\sum_{I\subset \{1,\cdots,n\}} (-1)^{|I|}\cdot |A_I|
\end{equation*}
where the summation runs over all subsets $I$ of $\{1,\cdots,n\}$ and $A_I$ denotes the set of elements having all the properties of $I$.

This is perfectly fine, but he finishes his two-page paper with a Generalized version of Inclusion-Exclusion Principle.

Let $t_1,\cdots,t_n$ be commuting indeterminates and for
$I=\{i_1,\cdots,i_k\} \subseteq\{1,\cdots,n\}$ denote
$t_I=t_1\cdots t_k$ and $(t-1)_{I}=(t_{i_1} – 1)\cdots(t_{i_k}-1)$.
For $a\in A$, let $prop(a)$ denotes the set of properties of $a$. Then
\begin{equation*}\sum_{a\in A}t_{prop(a)} = \sum_{I\subset\{1,\cdots,n\}}|A_I|\cdot (t-1)_I\end{equation*}

I’ve never heard of this generalized version before. Probably, the original version can be recovered by setting $t_{i_1}=\cdots=t_{i_k}=0$ and the LHS becomes ‘number of elements with no properties at all.’ Is there any textbooks or lecture notes explaining this generalized version of Inclusion-Exclusion Principle?

#### Solutions Collecting From Web of "A Generalized version of Inclusion-Exclusion Principle?"

I’ve not seen it before, but I can derive it. For $I\in[n]=\{1,\ldots,n\}$ let $x_i=t_i-1$. Then

\begin{align*} \sum_{a\in A}t_{prop(a)}&=\sum_{a\in A}\prod_{i\in prop(a)}(x_i+1)\\ &=\sum_{a\in A}\sum_{I\subseteq prop(a)}x_I\\ &=\sum_{I\subseteq[n]}\sum_{a \in A_I}x_I\\ &=\sum_{I\subseteq[n]}|A_I|x_I\\ &=\sum_{I\subseteq[n]}|A_I|(t-1)_I\;, \end{align*}

where $x_I=\prod_{i\in I}x_i$.

If all of the indeterminates are the same, it becomes

$$\sum_{a\in A}t^{|prop(a)|}=\sum_{I\subseteq[n]}|A_I|(t-1)^{|I|}\;,$$

which is essentially the result presented in Section $4.2$, A generatingfunctionological view of the sieve method, in Herbert S. Wilf’s book generatingfunctionology, which is freely available here.