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