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?

up vote 2 down vote accepted

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

  • Wow, thanks -- I got not just the reference but also a nice book that I didn't know about! :-) – joriki Jun 1 '16 at 14:02
  • You're welcome! – Hans Lundmark Jun 1 '16 at 14:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.