Unexpected formulas for "exactly $k$ sets" and "at least $k$ sets" variations of the principle of inclusion-exclusion

Question

There are two formulas that I have derived, and the difference between them is puzzling me. Let $n$ be a positive integer and $A_1,A_2,\ldots, A_n$ be finite sets, and let $k$ be an integer such that $1\le k\le n.$

1. The number of elements of $\displaystyle \bigcup_{i=1}^{n}{A_i}$ that lie in exactly $k$ of the $A_i$ is $$\sum_{m=k}^{n}{(-1)^{m+k}\binom{m}{k}\sum_{\substack{J\subseteq[n]\\ |J|=m}}{\left|\bigcap_{j\in J}A_{j}\right|}}.$$
2. The number of elements of $\displaystyle \bigcup_{i=1}^{n}{A_i}$ that lie in at least $k$ of the $A_i$ is $$\sum_{m=k}^{n}{(-1)^{m+k}\binom{m-1}{k-1}\sum_{\substack{J\subseteq[n]\\ |J|=m}}{\left|\bigcap_{j\in J}A_{j}\right|}}.$$

Here, $[n]$ denotes the section $\{1,2,3,\ldots, n\}$ of the positive integers. I am fairly certain that these formulas are correct, as I have tested them in various specific and general cases. For example, $k=1$ in the second formula yields the ordinary PIE formula. In fact, I used the first formula in conjunction with combinatorial identities to prove the second one; and I know that the first formula is true using a combinatorial proof.

Anyway, here is my dilemma: For fixed $n$ and $k,$ the second expression is greater than or equal to the first expression. This just seems weird to me because the second expression involves the binomial coefficients of the row above the row in which the binomial coefficients of the first expression lie in Pascal's triangle. I would have expected it to be the other way around. It seems that the alternating signs somehow produce this counterintuitive result, which I have proven but have been unable to fathom. Is there an explanation for this? Is the inequality resulting from saying the second expression is greater than or equal to the first expression evident in some larger theorem or context?

As a side note, I was also wondering if this is in some way connected to the Bonferroni inequalities. This is just something I was musing about, inspired by the similarity in form and context, but I'm not too hopeful about it as the stated formulas have binomial coefficients, which Bonferroni does not.

Answer 1

We can simplify the question by focussing on a specific element $x\in\bigcup_{j=1}^nA_j$ and check how often it is counted in both expressions. Let's assume $x$ is element in exactly $q$ sets $A_j$, $j\in J\subseteq [n]$, $|J|=q, k\leq q\leq n$. Due to symmetry we can WLOG assume \begin{align*} x\in\left(\bigcap_{j=1}^qA_q\right)\setminus\left(\bigcup_{k=q+1}^n A_{k}\right)\tag{1} \end{align*}

Since $x$ is counted in $\sum_{{J\subseteq[q]}\atop{ |J|=m}}{\left|\bigcap_{j\in J}A_{j}\right|}$ with $k\leq m\leq q$ exactly $\sum_{{J\subseteq[q]}\atop{ |J|=m}}1=\binom{q}{m}$ times due to (1), the first expression boils down to \begin{align*} \color{blue}{\sum_{m=k}^q}&\color{blue}{(-1)^{m-k}\binom{m}{k}\binom{q}{m}}\\ &=\binom{q}{k}\sum_{m=k}^q(-1)^{m-k}\binom{q-k}{m-k}\\ &=\binom{q}{k}\sum_{m=0}^{q-k}(-1)^{m}\binom{q-k}{m}\\ &=\binom{q}{k}(1-1)^{q-k}\\ &\,\,\color{blue}{=\begin{cases}1\qquad&q=k\\0\qquad&q>k\end{cases}} \end{align*} showing that $x$ is counted once iff it is element in exactly $k$ sets $A_j$, $j\in J\subseteq [n]$ and zero times otherwise.

Now we consider the second expression with $x$ being an element in exactly $q$ sets $A_j$ as given in (1).

We obtain \begin{align*} \color{blue}{\sum_{m=k}^q}&\color{blue}{(-1)^{m-k}\binom{m-1}{k-1}\binom{q}{m}}\\ &=\sum_{m=k}^q(-1)^{m-k}\frac{k}{m}\binom{m}{k}\binom{q}{m}\\ &=\binom{q}{k}\sum_{m=k}^q(-1)^{m-k}\frac{k}{m}\binom{q-k}{m-k}\\ &=\binom{q}{k}\sum_{m=0}^{q-k}(-1)^{m}\frac{k}{m+k}\binom{q-k}{m}\\ &=k\binom{q}{k}\sum_{m=0}^{q-k}(-1)^{m}\int_{0}^1z^{m+k-1}\,dz\binom{q-k}{m}\\ &=k\binom{q}{k}\int_{0}^1z^{k-1}\left(\sum_{m=0}^{q-k}(-1)^{m}z^m\binom{q-k}{m}\right)\,dz\\ &=k\binom{q}{k}\int_{0}^1z^{k-1}(1-z)^{q-k}\,dz\tag{2}\\ &=k\binom{q}{k}B(k,q-k+1)\tag{3}\\ &\,\,\color{blue}{=1} \end{align*} showing that $x$ is counted once iff it is element in exactly $q$ sets $A_j$ with $k\leq q\leq n$.

Comment

• In (2) we use the Beta function $B(k,q-k+1)=\frac{\Gamma(k)\Gamma(q-k+1)}{\Gamma(q+1)}$.

• In (3) we use $B(k,q-k+1)=\frac{(k-1)!(q-k)!}{q!}=\frac{1}{k}\binom{q}{k}^{-1}$.

Answer 2

These are shown in this answer as a Theorem (Generalized Inclusion-Exclusion Principle) and Corollary 2.

Given that the number of items in exactly $k$ sets is $\sum\limits_{m=k}^n(-1)^{m-k}\binom{m}{k}N(m)$, the number of items in at least $p$ sets is $$ \begin{align} \sum_{k=p}^n\sum_{m=k}^n(-1)^{m-k}\binom{m}{k}N(m) &=\sum_{m=p}^n\sum_{k=p}^m(-1)^{m-k}\binom{m}{k}N(m)\tag1\\ &=\sum_{m=p}^n(-1)^{m-p}\sum_{k=p}^m\binom{-1}{k-p}\binom{m}{m-k}N(m)\tag2\\ &=\sum_{m=p}^n(-1)^{m-p}\binom{m-1}{m-p}N(m)\tag3\\ &=\sum_{m=p}^n(-1)^{m-p}\binom{m-1}{p-1}N(m)\tag4 \end{align} $$ Explanation:
$(1)$: change of order of summation
$(2)$: $\binom{-1}{k-p}=(-1)^{k-p}[k\ge p]$ (Iverson brackets)
$(3)$: Vandermonde's Identity
$(4)$: symmetry of Pascal's Triangle

As long as we assume that $\sum\limits_{m=k}^n(-1)^{m-k}\binom{m}{k}N(m)\ge0$ for all $k$, we get that $$ \sum\limits_{m=k}^n(-1)^{m-k}\binom{m-1}{k-1}N(m)\ge\sum\limits_{m=k}^n(-1)^{m-k}\binom{m}{k}N(m)\tag5 $$