Generalised inclusion-exclusion principle

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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*}

Answer 5

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