Combinatorics meaning of $L_m=\sum_{j=m}^{n}(-1)^{j-m}\binom{j-1}{m-1}S_j$

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:

$$E(z)=L(z-1)$$

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.)

• 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. – darij grinberg Oct 7 '18 at 0:51
• 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".) ... – darij grinberg Oct 25 '18 at 21:11
• ... 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 ... – darij grinberg Oct 25 '18 at 21:15
• ... 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. – 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, 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, 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, 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).

• 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! – linear_combinatori_probabi Aug 26 at 17:52
• @FtyRain: Yes, you're right. Many thanks for pointing at it. I will correct it soon. – 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$$.