1
$\begingroup$

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?
$\endgroup$
2
$\begingroup$

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.


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