19
$\begingroup$

In answers to combinatorial questions, I sometimes use the fact that if there are $a_k$ ways to choose $k$ out of $n$ conditions and fulfill them, then there are

$$ \sum_{k=j}^n(-1)^{k-j}\binom kja_k $$

ways to fulfill exactly $j$ of the conditions. This is true because a case in which exactly $m$ of the conditions are fulfilled is counted $\binom mk$ times in $a_k$ and thus contributes

$$ \sum_{k=j}^n(-1)^{k-j}\binom kj\binom mk=\delta_{jm}\;. $$

In particular, if the number of ways of fulfilling $k$ particular conditions is the same, $b_k$, for all choices of the $k$ conditions, then $a_k=\binom nkb_k$ and there are

$$ \sum_{k=j}^n(-1)^{k-j}\binom kj\binom nkb_k $$

ways to fulfill exactly $j$ of the conditions.

I found that inclusion-exclusion seems to be almost exclusively applied to the case $j=0$, to find the number of ways to fulfill none (or, complementarily, at least one) of the conditions, and that many, even very experienced users are not familiar with this generalisation. That prompted me to look around for a reference for it, but I couldn't find one. So my questions are:

Is this more general inclusion-exclusion principle well-known?
If so, could you provide a reference for it that I could point to when asked about it?

$\endgroup$
5
  • 2
    $\begingroup$ The answers to these questions might also be helpful: math.stackexchange.com/questions/1632896 math.stackexchange.com/questions/100299 $\endgroup$
    – user84413
    Jun 1, 2016 at 15:23
  • $\begingroup$ I have deleted my former comments because my answer makes them redundant and is more in accordance with your use of indices. $\endgroup$
    – drhab
    Mar 17, 2020 at 16:37
  • $\begingroup$ If you choose $k$ out of $n$ conditions and fulfill them, isn't this equivalent to that you fulfill exactly $k$ of the conditions? I still prefer $a_k$ to be number of elements "has at least $k$ conditions" or "identified by $k$ conditions". $\endgroup$ Sep 3, 2020 at 21:39
  • 1
    $\begingroup$ @linear_combinatori_probabi: No, that's not equivalent. The first part, "choose $k$ out of $n$ conditions and fulfill them" doesn't say "exactly", so these $k$ conditions need to be fulfilled but others might be as well. The point is that it's usually easier to count the ways to fulfill $k$ particular conditions than to count the ways to fulfill exactly $k$ particular conditions (while violating all the others). $\endgroup$
    – joriki
    Oct 8, 2020 at 9:42
  • $\begingroup$ This looks similar to the Generalized Inclusion-Exclusion Principle from this answer. I have searched and found The Inclusion Exclusion Principle and Its More General Version by Stewart Weiss, which I believe may imply my result, but that paper has abstracted things so much that it is hard to tell without more thought. $\endgroup$
    – robjohn
    Aug 26, 2021 at 15:01

5 Answers 5

7
$\begingroup$

This is Corollary 5.2 on p. 184 of Martin Aigner's excellent book A Course in Enumeration.


Reproduced from A Course in Enumeration

Using the notation $$ \begin{align} N_{\supseteq T}&:=\#\{x\in X:x\text{ possesses }\textit{at least}\text{ the properties in $T$}\},\\ N_{=T}&:=\#\{x\in X:x\text{ possesses }\textit{precisely}\text{ the properties in $T$}\}, \end{align}\tag2 $$

$\ \ \ \vdots$

Corollary $\boldsymbol{5.2}$. Let $X$ be a universe, $E=\{e_1,\dots,e_n\}$ a set of properties, and $N_p$ the number of elements in $X$ that possess precisely $p$ properties. Then $$ N_p=\sum_{k=p}^n(-1)^{k-p}\binom{k}{p}\sum_{T:|T|=k}N_{\supseteq T}.\tag{12} $$ In particular, if $E$ is homogeneous, then $$ N_p=\binom{n}{p}\sum_{k=p}^n(-1)^{k-p}\binom{n-p}{k-p}N_{\ge k}.\tag{13} $$

$\endgroup$
5
  • $\begingroup$ I was just able to take a look at that Corollary, and it is essentially what is given in this answer. It would be better, of course, if more of the answer were given here rather than requiring the reader to acquire this book. $\endgroup$
    – robjohn
    Mar 5, 2022 at 10:10
  • $\begingroup$ @robjohn: The question specifically asked for a reference to point to, so that's what I gave. The results are already described in the question itself... $\endgroup$ Mar 5, 2022 at 11:30
  • $\begingroup$ The question does ask for a reference-request, and you gave that. I am not saying your answer is inappropriate; however, I stand by my statement that it would more useful if the answer were more self-contained. For example, if the statement of Corollary 5.2 were included (with proper attribution, which you have given), I would have found this answer useful 5 years ago. This meta post is relevant, and How do I write a good answer? supports this under "Provide context for links". $\endgroup$
    – robjohn
    Mar 5, 2022 at 15:20
  • $\begingroup$ I have written up Corollary 5.2 in MathJax if you would like me to edit it into your question. $\endgroup$
    – robjohn
    Mar 5, 2022 at 15:21
  • $\begingroup$ @robjohn: Certainly, go ahead! Thanks for your effort. $\endgroup$ Mar 5, 2022 at 18:17
4
$\begingroup$

Another reference is section IV.3, "The Realization of m Among N Events", in An Introduction to Probability Theory and Its Applications, Volume I, Third Edition by William Feller, p. 106.

$\endgroup$
4
$\begingroup$

The answers to Probability of choosing envelopes made me realize that there is actually a straightforward combinatorial proof of this principle.

Denote by $C$ the set of conditions and by $c_{S\ell}$ the number of ways to fulfill the conditions in $S\subseteq C$ and exactly $\ell$ more. By standard inclusion–exclusion, the number of ways to fulfill exactly the conditions in $S$ is

$$ \sum_{\ell=0}^{|C|-|S|}(-1)^\ell c_{S\ell}\;. $$

Thus the number of ways to fulfill exactly $j$ conditions is

\begin{eqnarray} \sum_{S\subseteq C\atop|S|=j}\sum_{\ell=0}^{|C|-|S|}(-1)^\ell c_{S\ell} &=& \sum_{\ell=0}^{n-j}\sum_{S\subseteq C\atop|S|=j}(-1)^\ell c_{S\ell} \\ &=& \sum_{\ell=0}^{n-j}(-1)^\ell\binom{j+\ell}ja_k \\ &=& \sum_{k=j}^n(-1)^{k-j}\binom kja_k \;, \end{eqnarray}

since each set $S$ with $|S|=j$ appears $\binom{j+\ell}j$ times.

This also suggests another form of the specialized result for the case where the number of ways to fulfill $k$ conditions is the same, $b_k$, for all choices of the $k$ conditions. In that case we have $c_{S\ell}=\binom{n-j}\ell b_{j+\ell}$ independent of $S$, and the first sum above is the same for all $\binom nj$ choices of $j$ conditions, so the count is

$$ \binom nj\sum_{\ell=0}^{n-j}(-1)^\ell \binom{n-j}\ell b_{j+\ell} =\binom nj\sum_{k=j}^n(-1)^{k-j}\binom{n-j}{k-j}b_k\;, $$

and as

$$ \binom nj\binom{n-j}{k-j}=\binom kj\binom nk\;, $$

this coincides with

$$ \sum_{k=j}^n(-1)^{k-j}\binom kj\binom nkb_k\;, $$

but with the advantage that one of the binomial coefficients is constant and can remain outside the sum.

$\endgroup$
0
2
$\begingroup$

Here are some additional references:

  • Enumerative Combinatorics, Vol. I by R. P. Stanley: From chapter 2 Sieve Methods', Exercise 3:

    Let $S=\{P_1,\ldots,P_n\}$ be a set of properties, and let $f_k$ (respectively, $f_{\geq k}$) denote the number of objects in a finite set $A$ that have exactly $k$ (resp., at least $k$) of the properties. Show that \begin{align*} f_k&=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i,\qquad\qquad\quad\ \mathrm{and}\\ f_{\geq k}&=\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}g_i\qquad\qquad \mathrm{where}\\ g_{i}&=\sum_{{T\subseteq S}\atop{\#T=i}}f_{\geq}(T) \end{align*}

    An interesting note at the end of the given solution: An extensive bibliography appears in L. Takács, On the method of inclusion and exclusion, J. Amer. Stat. Soc. 62 (1967) .

  • Combinatorial Problems and Exercises by László Lovász. From chapter 2: The Sieve, Example 7a:

    Let $A_1,\ldots,A_n$ be arbitrary events of a probability space $(\Omega,P)$. For each $I\subseteq\{1,\ldots,n\}$, let \begin{align*} A_I&=\prod_{i\in I}A_i;\qquad A_{\emptyset}=\Omega;\qquad\qquad\mathrm{and\ let}\\ \sigma_k&=\sum_{|I|=k}P(A_I),\qquad\sigma_0=1. \end{align*} the probability that exactly $q$ of them occur is \begin{align*} \sum_{j=q}^n(-1)^{j+q}\binom{j}{q}\sigma_j \end{align*}

  • An Introduction to Combinatorial Analysis by J. Riordan. From chapter 3 The Principle of Inclusion and Exclusion, section 3 Symbolic Development:

    In the same notation, $p(k)$ is the relative number of objects with exactly $k$ of the given properties, ... Then ... \begin{align*} p(k)&=S_k-(k+1)S_{k+1}+\binom{k+2}{2}S_{k+2}-\cdots+(-1)^{n-k}\binom{n}{k}S_n\\ &=S^k(1+S)^{-k-1},\qquad S^k\equiv S_k \end{align*}

  • Advanced Combinatorics - The Art of Finite and Infinite Expansions by L. Comtet. From chapter IV Sieve Formulas, Section 4.8: Formulas of Ch. Jordan:

    Theorem A ([Charles Jordan, 1926, 1927, 1934, 1939]). Let $N_r(\mathcal{A})$ stand for the set of points of $N$ that are covered by exactly $r$ subsets of the system $\mathcal{A}=(A_1,A_2,\ldots,A_p)$, then we have for every measure $f\in\mathcal{M}(N,b(\mathcal{A}))$: \begin{align*} f(N_r(\mathcal{A}))&=\sum_{x\in\mathcal{P}_{\geq r}[p]} (-1)^{|x|-r}\binom{|x|}{r}f(A_{x})\\ &=\sum_{r\leq k\leq p}(-1)^{k-r}\binom{k}{r}S_k \end{align*}

$\endgroup$
1
$\begingroup$

"I sometimes use the fact that if there are $a_{k}$ ways to choose $k$ out of $n$ conditions and fulfill them..."

In this answer I choose for a setup starting with a set $X$ containing what you call ways as elements. Each of the $n$ conditions corresponds with a subset of $X$ that contains exactly the ways to fulfill the condition.

So let me introduce an index set $I$ with cardinality $n$ and the collection $\left\{ A_{i}\mid i\in I\right\} $ where $A_{i}\subseteq X$ contains the ways that fulfill condition $i$.

For $J\subseteq I$ we define: $$A_{J}:=\bigcap_{i\in J}A_{i}$$ under the convention that $A_{\varnothing}=X$.

Then $a_{k}$ mentioned above can be recognized as: $$a_k=\sum_{J\subseteq I\wedge\left|J\right|=k}\left|A_{J}\right|$$

In the special case where the cardinality of $J$ is determining for the cardinality of $A_{J}$ and $b_{k}:=\left|A_{J}\right|$ whenever $\left|J\right|=k$ we have the equality: $$a_{k}=\binom{n}{k}b_{k}$$ which is also mentioned in your question.

Finally for nonnegative integer $j$ we define: $$U_{j}:=\left\{ x\in X\mid\sum_{i\in J}\mathbf{1}_{A_{i}}\left(x\right)=j\right\}\text{ and }u_j:=|U_j| $$

So that we will have $x\in U_{j}$ iff $x$ is a way that fulfills exactly $k$ of the conditions, and - as you said in your question - we will have: $$u_{j}=\sum_{k=j}^{n}\left(-1\right)^{k-j}\binom{k}{j}a_{k}\tag1$$

Uptil now I only sketched the setup and now it is time to find combinatorial proof of this.


Lemma: If $S$ is a finite and non-empty set then: $$|\{T\in\mathcal P(S)\mid |T|\text{ is odd}\}|=|\{T\in\mathcal P(S)\mid |T|\text{ is even}\}|$$

Proof: Straightforward.


Theorem: For every nonnegative integer $j$ we have: $$\mathbf{1}_{U_{j}}+\sum_{J\subseteq I\wedge\left|J\right|-j\text{ is odd}}\binom{\left|J\right|}{j}\mathbf{1}_{A_{J}}=\sum_{J\subseteq I\wedge\left|J\right|-j\text{ is even}}\binom{\left|J\right|}{j}\mathbf{1}_{A_{J}}$$


Before proving the theorem let us first have a look at its impact.

If some measure $\mu$ is involved and we are dealing with measurable sets then integration on both sides yields: $$\mu\left(U_{j}\right)+\sum_{J\subseteq I\wedge\left|J\right|-j\text{ is odd}}\binom{\left|J\right|}{j}\mu\left(A_{J}\right)=\sum_{J\subseteq I\wedge\left|J\right|-j\text{ is even}}\binom{\left|J\right|}{j}\mu\left(A_{J}\right)$$ If we take the counting measure then automatically the sets are measurable and at first hand we find: $$u_{j}+\sum_{k=j\wedge k-j\text{ is odd}}^{n}\binom{k}{j}a_{k}=\sum_{k=j\wedge k-j\text{ is even}}^{n}\binom{k}{j}a_{k}$$ where $a_{k}$ and $u_{j}$ are defined as above.

If moreover the $a_{k}$ are finite then we can subtract without problems so that we arrive at: $$u_{j}=\sum_{k=j}^{n}\left(-1\right)^{k-j}\binom{k}{j}a_{k}\tag1$$

So $(1)$ follows immediately from the theorem and is not more than a special case.

Surprisingly the theorem is not difficult to prove and the only essential thing needed for that is the lemma.


Proof:

Let $x\in X$.

Then it is enough to prove that substituting $x$ on both sides gives equal outcomes. For this let: $$I_{x}:=\left\{ i\in I\mid x\in A_{i}\right\} $$ and discern the following cases:

$\left|I_{x}\right|<j$ then we find $0+0=0$ on LHS and $0$ on RHS.

$\left|I_{x}\right|=j$ then we find $1+0=1$ on LHS and $1$ on RHS.

$\left|I_{x}\right|>j$ then we find: $$0+\sum_{J\subseteq I_{x}\wedge\left|J\right|-j\text{ is odd}}\binom{\left|J\right|}{j}\binom{\left|I_{x}\right|}{\left|J\right|}=\binom{\left|I_{x}\right|}{j}\sum_{J\subseteq I_{x}\wedge\left|J\right|-j\text{ is odd}}\binom{\left|I_{x}\right|-j}{\left|J\right|-j}$$ on LHS and: $$\binom{\left|I_{x}\right|}{j}\sum_{J\subseteq I_{x}\wedge\left|J\right|-j\text{ is even}}\binom{\left|I_{x}\right|-j}{\left|J\right|-j}$$ on RHS.

The factor $\binom{\left|I_{x}\right|}{j}$ on both sides can be striped away and what remains is exactly the true statement that the number of subsets of a set having the finite cardinality $\left|I_{x}\right|-j>0$ with odd cardinality equals the number of subsets with even cardinality. So the content of the lemma.

This completes the proof.


This is not very difficult combinatorial proof of what you call the general version of inclusion/exclusion and is built on not more than one very simple lemma.

$\endgroup$

You must log in to answer this question.

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