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

Solution 1:

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

Solution 2:

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