Generalised inclusion-exclusion principle

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?


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


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.


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.