Let $U$ a universe and there are $n$ properties defined on it: $a_1,a_2,\dots,a_n$. Define the sum of the size of all $m$-intersection(s) of $A_i=\{x\in U|x\textrm{ has property }a_i\}$ to be: $S_m=\sum_{|I|=m}\left|\bigcap_{i\in I}A_i\right|$.

Now let $L_m$ counts the number of elements have at least $m$ properties, then

$$L_m=S_m-{m\choose m-1}S_{m+1}+{m+1\choose m-1}S_{m+2}-\dots+(-1)^{n-m}{n-1\choose m-1}S_n.$$

Is there any combinatorial way to explain the meaning of these coefficients?

The strange thing is that: Let $E_m$ counts the number of elements have exactly $m$ properties, then

$$E_m=S_m-{m+1\choose m}S_{m+1}+{m+2\choose m}S_{m+2}-\dots+(-1)^{n-m}{n\choose m}S_n,$$

and we can obtain $L_m$ by modifying $E_m$: for each coefficient $j\choose k$ of $E_m$, the corresponding one is $j-1\choose k-1$ for $L_m$.

This observation seems related to the shift by one property pointed out in a very great answer [https://math.stackexchange.com/a/809201/390226] by Mr. @Markus Scheuer:


which $E(z)$ and $L(z)$ are two generating functions

\begin{align*} L(z) = \sum_{k=0}^{n}l_kz^k\qquad\qquad E(z)=\sum_{k=0}^{n}e_kz^k \end{align*}

(Notice that $e_k$ is correspond to my $E_m$, and $l_k$ to $S_m$ in my question above.)

  • 3
    $\begingroup$ Your definition of $S_i$ looks off -- is it a set, or a number? I suspect your formula for $E_m$ is supposed to be Charles Jordan's generalized inclusion-exclusion principle (equality $(\ast)$ in Ottavio D’Antona, Gian-Carlo Rota, Two Rings Connected with the Inclusion-Exclusion Principle, or Theorem 3.44 in my Notes on the combinatorial fundamentals of algebra, version of 4 October 2018). I don't know a combinatorial proof right off my head, but it's an interesting question. $\endgroup$ – darij grinberg Oct 7 '18 at 0:51
  • $\begingroup$ I can only give hints, for lack of time. First of all, use the standard trick: If $Z$ is a subset of $U$, then $\left|Z\right| = \sum\limits_{u \in U} \left[u \in Z\right]$, where we are using the Iverson bracket notation. Thus you can write all of the $L_i$, $E_i$ and $S_i$ as sums over $u \in U$. Prove the equalities for each addend separately; this reduces the problem to the case when $U$ is a $1$-element set. (In combinatorial terms, this means "fixing an element $u \in U$ and seeing how often it gets counted on both sides".) ... $\endgroup$ – darij grinberg Oct 25 '18 at 21:11
  • $\begingroup$ ... Thus, to prove your first equality, you need to check that each $u \in U$ satisfies $\left[u \in A_i \text{ for at least $m$ many $i$}\right] = \sum\limits_{p \geq m} \left(-1\right)^{p-m} \dbinom{p-1}{m-1} \sum\limits_{P \text{ is a $p$-element subset of } \left\{1,2,\ldots,n\right\}} \left[u \in A_i \text{ for each } i \in P \right]$. Fix $u \in U$, and let $G = \left\{ i \in \left\{1,2,\ldots,n\right\} \mid u \in A_i \right\}$. Then, this equality rewrites ... $\endgroup$ – darij grinberg Oct 25 '18 at 21:15
  • $\begingroup$ ... as $\left[\left|G\right| \geq m\right] = \sum\limits_{p \geq m} \left(-1\right)^{p-m} \dbinom{p-1}{m-1} \dbinom{\left|G\right|}{p}$. But this is a simple combinatorial identity, and shouldn't be hard to prove by the DIE method. $\endgroup$ – darij grinberg Oct 25 '18 at 21:17

This is a rather pragmatic, semi-combinatorial answer. Nevertheless it might be useful for some more creative combinatorialists. We provide an interpretation of the binomial coefficients of $E_m$ and derive from them an interpretation of the binomial coefficients of $L_m$.

At first I'd like to introduce a slightly different notation.

Let $P=\{a_1,a_2,\ldots,a_n\}$ denote a set of properties and let $U$ be a finite set with elements having zero or more properties from $P$. We use the somewhat more suggestive notation $E_{=m}$ and $L_{\geq m}$ instead of $E_m$ and $L_m$. OP's formula can now be written as \begin{align*} L_{\geq m}&=\sum_{j=m}^n(-1)^{j-m}\binom{j-1}{m-1}S_j\\ E_{=m}&=\sum_{j=m}^n(-1)^{j-m}\binom{j}{m}S_j\\ \end{align*} We also derive a somewhat different representation for $S_j$ which might be useful when analysing the situation. Let $Q\subset P$ be a subset of properties from $P$. We denote with \begin{align*} L_{\geq}(Q)&=\{x\in U: x \text{ has at least the properties in } Q\}\\ E_{=}(Q)&=\{x\in U: x \text{ has exactly the properties in } Q\}\\ \end{align*} Using this notation we can write \begin{align*} S_j=\sum_{{Q\subseteq P}\atop{|Q|=j}}L_{\geq }(Q)\qquad\text{and}\qquad L_{\geq }(Q)=\sum_{Q\subseteq R\subseteq P}E_{=}(R) \end{align*}

Interpretation of binomial coefficients of $E_{=m}$:

We consider \begin{align*} E_{=m}&=\sum_{j=m}^n(-1)^{j-m}\binom{j}{m}S_j\\ &=\binom{m}{m}S_m-\binom{m+1}{m}S_{m+1}+\binom{m+2}{m}S_{m+2}+\cdots+(-1)^{n-m}\binom{n}{m}S_n\tag{1} \end{align*} $E_{=m}$ counts the sets with elements having exactly $m$ properties. We consider subsets of $P$ of size $m$, $m+1$, up to $n$ and analyse how often each of them is counted.

  • $S_m$: We start with a subset of $P$ of size $m$ and take wlog $Q_m=\{a_1,a_2,\ldots,a_m\}$.

    The $m$-element set $Q_m$ is contained in $S_m$ but in no other set $S_j$ with $m<j\leq n$, since $S_j$ counts sets having at least $j$ elements. We see, the coefficient $\color{blue}{\binom{m}{m}}=1$ counts the number of occurrences of the $m$-element sets in $P$.

  • $S_{m+1}$: We consider wlog $Q_{m+1}=\{a_1,a_2,\ldots,a_{m+1}\}$.

    The $(m+1)$-element set $Q_{m+1}$ is contained in $S_m$ and $S_{m+1}$, but in no other set $S_j$ with $m+1<j\leq n$, since $S_j$ counts sets having at least $j$ elements. Note that $Q_{m+1}$ occurs $\binom{m+1}{m}$ times in $S_m$, since we can select $m$ properties from $Q_{m+1}$ in $\binom{m+1}{m}$ ways. Of course $Q_{m+1}$ occurs exactly once in $S_{m+1}$.

    We conclude the binomial coeffcient $\color{blue}{\binom{m+1}{m}}$ of $S_{m+1}$ is the compensation for overcounting $Q_{m+1}$ in $S_m$ and the same holds for all other sets of size $m+1$.

We can now generalise:

  • $S_{m+k}$: We consider wlog $Q_{m+k}=\{a_1,a_2,\ldots,a_{m+k}\}$ with $m+k\leq n$.

    The $(m+k)$-element set $Q_{m+k}$ is contained in $S_m,S_{m+1},\ldots,S_{m+k}$, but in no other set $S_j$ with $m+k<j\leq n$, since $S_j$ counts sets having at least $j$ elements.

We conclude the binomial coefficient $\color{blue}{\binom{m+k}{m}}$ of $S_{m+k}$ is the compensation for overcounting $Q_{m+k}$ in $S_m,S_{m+1},\ldots,S_{m+k-1}$ and the same holds for all other sets of size $m+k$.

Interpretation of binomial coefficients of $L_{\geq m}$:

We have \begin{align*} L_{\geq m}&=\sum_{j=m}^{n}(-1)^{j-m}\color{blue}{\binom{j-1}{m-1}}S_j\\ &=\binom{m-1}{m-1}S_m-\binom{m}{m-1}S_{m+1}+\cdots+(-1)^{n-m}\binom{n-1}{m-1}S_n\tag{2} \end{align*}

On the other hand we have \begin{align*} L_{\geq m}&=\sum_{k=m}^nE_{=k}\\ &=\sum_{k=m}^n\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}S_j\\ &=\sum_{m\leq k\leq j\leq n}(-1)^{j-k}\binom{j}{k}S_j\\ &=\sum_{j=m}^n\sum_{k=m}^j(-1)^{j-k}\binom{j}{k}S_j\\ &=\sum_{j=m}^n(-1)^{j-m}\left(\color{blue}{\sum_{k=m}^j(-1)^{k-m}\binom{j}{k}}\right)S_j\tag{3} \end{align*}

We conclude from (2) and (3) the coefficient \begin{align*} \color{blue}{\binom{j-1}{m-1}=\sum_{k=m}^j(-1)^{k-m}\binom{j}{k}} \end{align*} of $S_j$ is the compensation of overcounting according to the binomial coefficients of $S_k, m\leq k\leq j$ from $E_m, E_{m+1}, \ldots, E_{j}$.

Note: In order to see some more aspects regarding $\binom{j}{m}$, the coefficient of $S_j$ in $E_m$, we give here a proof of (1) following (2.39) in Richard P. Stanleys Enumerative Combinatorics, Vol. 1, Ed.02.

We obtain \begin{align*} \color{blue}{\sum_{j=m}^n}&\color{blue}{(-1)^{j-m}\binom{j}{m}S_j}\\ &=\sum_{j=m}^n(-1)^{j-m}\binom{j}{m}\sum_{{Q\subseteq P}\atop{|Q|=j}}L_{\geq} (Q)\\ &=\sum_{j=m}^n(-1)^{j-m}\binom{j}{m}\sum_{{Q\subseteq R\subseteq P}\atop{|Q|=j}}E_{=}(R)\\ &=\sum_{R\subseteq P}E_{=}(R)\sum_{Q \subseteq R}(-1)^{|Q|-m}\binom{|Q|}{m}\\ &=\sum_{R\subseteq P}E_{=}(R)\sum_{j=0}^{|R|}(-1)^{j-m}\binom{|R|}{j}\binom{j}{m}\\ &=\sum_{R\subseteq P}E_{=}(R)\binom{|R|}{m}\sum_{j=0}^{|R|}(-1)^{j-m}\binom{|R|-m}{|R|-j}\\ &=\sum_{R\subseteq P}E_{=}(R)\binom{|R|}{m}\delta_{|R|,m}\\ &\,\,\color{blue}{=E_{=m}} \end{align*} showing the validity of (1).

| cite | improve this answer | |
  • $\begingroup$ The $(m+1)$-element set $Q_{m+1}$ is contained in $S_m$ and $S_{m+1}$: Could you elaborate more about the phrase "is contained in" mean? I guess you mean: the elements with exactly $Q_{m+1}$ properties is counted in $S_m$ and $S_{m+1}$. Years past I now re-learn about this problem, thank you in advance! $\endgroup$ – linear_combinatori_probabi Aug 26 at 17:52
  • 1
    $\begingroup$ @FtyRain: Yes, you're right. Many thanks for pointing at it. I will correct it soon. $\endgroup$ – Markus Scheuer Aug 30 at 18:20

I think it is easier to visualize the formula for smaller n. For, n=3, you can use the standard Venn Diagram below.

$E_3=S_3$ is the central part $|A\cap B\cap C|$.

$E_2=|A\cap B \setminus A\cap B\cap C| +|A\cap C \setminus A\cap B\cap C|+|B\cap C \setminus A\cap B\cap C|.$

$S_2=|A\cap B | +|A\cap C |+|B\cap C|.$

Notice that $S_2$ counts the elements in $A\cap B\cap C$ three times.

The the second term on the right hand side of the $E_m$ formula removes the thrice counted elements from $A\cap B\cap C$.

$E_2= S_2 - {2+1\choose 1} S_3.$

$$ $$ $E_1= |A\setminus (B\cup C)| + |B\setminus (A\cup C)| + |C\setminus (A\cup B)|$.$

$S_1=|A| + |B| + |C|.$

Notice that $S_1$ counts the elements in $A\cap B \setminus A\cap B\cap C$ twice and counts the elements in $A\cap B \cap C$ three times.

$E_1= S_1 - {1+1\choose 1} S_2 + {1+2\choose 2} S_3.$

The second term removes the points in $A\cap B \setminus A\cap B\cap C$ from $S_1$ which were counted twice. The second term also corrects $S_1$ for the points in $A\cap C \setminus A\cap B\cap C$ and $B\cap C \setminus A\cap B\cap C$. However, the points in $A\cap B \cap C$ need to be removed also. The $S_1$ term counts these thrice. The ${1+1\choose 1} S_2$ term subtracts 6 for each point in $A\cap B \cap C$. The last term adds these points 3 times, so overall they have no effect on the right hand side.

You can repeat the same reasoning for any $n>3$ and $m\geq n-2$.

enter image description here

| cite | improve this answer | |

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.