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

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