4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.