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.
- 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$?
- 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.