6
$\begingroup$

I want to understand the meaning behind the coefficients of the following formula, $L_m$:

Let $U$ be a finite set, and there are $n$ properties defined on it: $a_1,a_2,\dots,a_n,$ and let $S_m$ denote the sum of all cardinalities of $m$-intersection(s) of $A_{1\le i\le n}, $ where $A_i=\{x\in U|x\textrm{ has property }a_i\}$. For example: $n=3,m=2, S_2=\sum_{1\le i\lt j\le3}|A_i\cap A_j|$. 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}\mp\dots+(-1)^{n-m}{n-1\choose m-1}S_n.$$

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


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

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

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

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

$\endgroup$
  • 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$ @darijgrinberg: Need your help~ $\endgroup$ – Ning Wang Oct 25 '18 at 18:28
  • $\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
1
+100
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @IsanaYashiro: Many thanks for accecpting my answer and granting the bounty. I've added a note which might be instructive. $\endgroup$ – Markus Scheuer Oct 29 '18 at 20:12
  • $\begingroup$ I'm grateful for your kindness and time! $\endgroup$ – Ning Wang Oct 30 '18 at 17:57
  • $\begingroup$ @IsanaYashiro: You're welcome. Many thanks for your nice comment. :-) $\endgroup$ – Markus Scheuer Oct 30 '18 at 21:30
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Your answer provide a good explanation of $E_m$, but could you elaborate more about $L_m$? I really want to know... $\endgroup$ – Ning Wang Oct 7 '18 at 5:00
  • 1
    $\begingroup$ I will take a look at it tomorrow. I really liked reading Scheuer's post. :) $\endgroup$ – irchans Oct 7 '18 at 6:20

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.