# How to interpret the Generalized Version of Inclusion-Exclusion Principle

This is a follow-up question on the previous post.

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*} |A_{\emptyset}| = \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$.

In Doron Zeilberger's paper, a generalized version of the Inclusion-Exclusion Principle is presented.

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*}

From the answer at the previous post, I know how to derive this generalized version. But I'm not sure about the meaning of this version.

1. I'm not sure about which values $t_I$ can have. For example, if all the $t_{i_k}$ is set to 1, the RHS is trivially zero. What does that mean? Can I just assume that $0 \leq t_{i_k} < 1$?
2. What does $t_{prop(a)}$ in the LHS of the generalized version mean? Is there any combinatorial problem that needs this generalized version?

I can’t (yet, anyway!) give you a good answer to the full question, but I can explain what the generalized version says when each $t_k\in\{0,1\}$; it isn’t quite what you think, because you’ve overlooked the convention that an empty product is $1$.

Let $t_k=0$ for $k=1,\ldots,n$. For $I\subseteq[n]$ let $B_I=\{a\in A:prop(a)=I\}$. Note that in that case

\begin{align*} t_{prop(a)}&=\begin{cases} 1,&\text{if }prop(a)=\varnothing\\ 0,&\text{if }prop(a)\ne\varnothing \end{cases}\\ &=\begin{cases} 1,&\text{if }a\in B_\varnothing\\ 0,&\text{if }a\in A\setminus B_\varnothing\;. \end{cases} \end{align*}

The generalized version then specializes to

$$|B_\varnothing|=\sum_{I\subseteq[n]}(-1)^{|I|}|A_I|\;,$$

the usual inclusion-exclusion principle. The set on the lefthand side really is $B_\varnothing$, not $A_\varnothing$ as in your question: $A_\varnothing=\{a\in A:\varnothing\subseteq prop(a)\}=A$.

If $t_k=1$ for $k=1,\ldots,n$, then $t_I=1$ for each $I\subseteq[n]$, while $(t-1)_I=1$ if $I=\varnothing$ and is $0$ otherwise, so in this case the generalized version specializes to the undeniably true by rather uninteresting $|A|=|A|$.

If $J\subseteq[n]$, and we set $t_k=0$ for $k\in J$ and $t_k=1$ for $k\in[n]\setminus J$, we find that

$$t_{prop(a)}=\begin{cases} 1,&\text{if }J\cap prop(a)=\varnothing\\ 0,&\text{if }J\cap prop(a)\ne\varnothing \end{cases}$$

and

$$(t-1)_I=\begin{cases} (-1)^{|I|},&\text{if }I\subseteq J\\ 0,&\text{if }I\nsubseteq J\;, \end{cases}$$

and the resulting special case is

$$\left|A\setminus\bigcup_{i\in J}A_i\right|=\sum_{I\subseteq J}(-1)^{|I|}|A_I|\;,$$

which is just the ordinary inclusion-exclusion principle for the set $J$ of properties (instead of the set $[n]$).

The case in which each $t_k=2$ also has a fairly straightforward interpretation. It’s convenient to let $n_a=|prop(a)|$ for $a\in A$. Then $(t-1)_I=1$ for each $I\subseteq[n]$, so we have

$$\sum_{a\in A}2^{n_a}=\sum_{I\subseteq[n]}|A_I|$$

or, equivalently,

$$\sum_{a\in A}\left|\wp\big(prop(a)\big)\right|=\sum_{I\subseteq[n]}|A_I|\;.$$

This basically just says that we can count the pairs $\langle a,I\rangle\in A\times\wp([n])$ such that $a\in A_I$ (equivalently, $I\subseteq prop(a)$) by conditioning on $a$ to get

$$\sum_{a\in A}\sum_{I\subseteq prop(a)}1=\sum_{a\in A}\left|\wp\big(prop(a)\big)\right|$$

or by conditioning on $I$ to get

$$\sum_{I\subseteq[n]}\sum_{a\in A_I}1=\sum_{I\subseteq[n]}|A_I|\;.$$

More generally, if $1\le m\in\Bbb Z^+$, and $t_k=m+1$ for $k=1,\ldots,n$, we have

$$\sum_{a\in A}(m+1)^{n_a}=\sum_{I\subseteq[n]}m^{|I|}|A_I|\;$$

I don’t know how likely it is to arise in practice, but this does have a fairly straightforward combinatorial interpretation. The lefthand side is the number of ways to pick an $a\in A$ and color its properties with at most $m+1$ colors. The righthand side is the number of ways to pick a set $I$ of properties, color them with at most $m$ colors, and pick an $a\in A$ that has all of the properties in $I$.

I don’t think that this is immediately obvious, though it can be derived from the binomial theorem without reference to this generalized inclusion-exclusion principle. Each $a\in A$ contributes $m^{|I|}$ to the righthand side for each $I\subseteq prop(a)$; there are $\binom{n_a}k$ such $I$ of cardinality $k$, so $a$ contributes

$$\sum_{k=0}^{n_a}\binom{n_a}km^k=(m+1)^{n_a}$$

to the righthand side as well as to the lefthand side.