4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Whenever an element lies in exactly $k$ of the $A_i$, it also lies in at least $k$ of the $A_i$. All the elements being counted in (1) are also counted in (2). Elements that lie in $k+1$ or more of the $A_i$ are not counted in (1), but are counted in (2). So, doesn't it make sense that the second number is at least as large? $\endgroup$
    – Toni
    May 15, 2020 at 22:01
  • $\begingroup$ Just looking at the individuals summands is misleading because some of them are larger and some smaller than 0. $\endgroup$
    – Toni
    May 15, 2020 at 22:04
  • $\begingroup$ It makes sense that the second expression is greater than or equal to the first one. I'm just bemused by the fact that we jumped back by one row in Pascal's triangle. $\endgroup$
    – Favst
    May 15, 2020 at 22:06
  • $\begingroup$ Maybe proving (2) in a different way might give some insight. Let $N_k$ denote the number of elements that are in exactly $k$ of the $A_i$. Then the number of elements at least in $k$ of the $A_i$ can be calculated as follows: $$ \left\lvert \bigcup_{i=1}^n A_i\right\rvert - \sum_{l=1}^{k-1} N_l = \left\lvert \bigcup_{i=1}^n A_i\right\rvert -\sum_{l=1}^{k-1}\sum_{m=l}^{n}{(-1)^{m+l}\binom{m}{l}\sum_{\substack{J\subseteq[n]\\ |J|=m}}{\left|\bigcap_{j\in J}A_{j}\right|}} = \ldots$$ $\endgroup$
    – Toni
    May 15, 2020 at 22:25
  • $\begingroup$ Maybe at some point one can use one of the identities for binomial coefficients for alternating sums. That might explain the shift one row up in the Pascal's triangle. Not sure if this leads anywhere, but it might be worth a try. $\endgroup$
    – Toni
    May 15, 2020 at 22:26

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .