# Inclusion-exclusion: Intuition for "exactly $k$ conditions"

TL;DR: I'm looking for intuition for the method by which we calculate the amount of elements that are in exactly $$m$$ subsets.

The "basic" case I've been taught for inclusion/exclusion is very intuitive to me. It claims that given $$n$$ subsets $$A_1, A_2, \ldots, A_n$$ of some set $$U$$, if we denote $$W_0=\left| U \right|$$ and $$W_k=\sum_{1 \leq i_1 < i_2<\ldots < i_k \leq n}\left| A_{i_1} \cap A_{i_2} \cap \ldots \cap A_{i_k} \right|$$ for all such $$k\in\mathbb{N}$$ that are larger than $$0$$, then:

$$\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{k=1}^{n}(-1)^{k+1}W_k$$

I also know how to prove it; but more to the point of this post: I have developed quite a sturdy intuition for why it is correct. That was done by playing around with Venn diagrams and observing that adding together the sizes of all subsets has many elements counted multiple times, which we fix by then subtracting everything that's in an intersection of any two subsets, but that's overkill and so we fix it by adding those in intersections of any three of the subsets to fix that, and so on and forth until we reach the intersection of all $$n$$ sets.

A bit further into the rabbit hole and I reach a wall that I find significantly harder to scale, however. I denote $$E(m)$$ as being the amount of elements that are in exactly $$m$$ of the subsets. So, for example, $$E(0)$$ would be elements that aren't in any of the sets, which gives us $$E(0)=\left|U\right|-\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{k=0}^{n}(-1)^{k}W_k$$. So far so good.

The problematic bit is when I try to look into $$E(m)$$ for any other (relevant) value of $$m$$.
I was given the following formula:
$$E(m)=\sum^n_{k=m}(-1)^{k-m} \binom{k}{m} W_k$$
And indeed, it works. Furthermore, I've been successful in proving it by taking an arbitrary $$x\in U$$, splitting it into cases based on the amount of subsets it's in, and showing that it "contributes the same value to each side" (which is $$1$$ $$\iff$$ it is in precisely $$m$$ such subsets, and $$0$$ otherwise).

My problem is that in this case, I don't have any intuition at all for this. I've been trying to play around with Venn diagrams as before, but something about that binomial coefficient multiplied by the $$W_k$$ just... doesn't currently click to me. I know sometimes intuition doesn't act in our best interest, and I know that sometimes we accept things based solely on their proof and not at all on the intuition behind them, and I'm totally fine with that, as long as I understand the proof; but in this particular case, though I do feel comfortable enough with the proof, I also feel like I could develop an intuition for this, and I'm just one simple and clear explanation short of doing so.

So this is what I'm here for!
I was hoping someone could provide a "convincing" explanation (using Venn diagrams, some direct combinatorial explanation, or anything else that comes to your mind) for this formula for $$E(m)$$ (amount of elements that are in exactly $$m$$ subsets, or that fulfill exactly $$m$$ conditions, or some other equivalent phrasing of this problem).

• Thanks a bunch in advance!
– Shay
Commented Oct 13, 2021 at 15:58
• There are a couple of proofs in the answers to this question: math.stackexchange.com/questions/1808129/… You might take a look and see if you find anything helpful. Commented Oct 14, 2021 at 15:18

When you count the number of elements in exactly $$m$$ subsets, you first count up the $$W_m$$. But every element that is in exactly $$m+1$$ subsets would be counted $${m+1} \choose m$$ times. So to componsate for that you subtract $$W_{m+1} {{m+1}\choose m}$$.

Now every element in exactly $$m+2$$ subsets will be first counted $${m+2}\choose m$$ times, and then compensated for $${m+2 \choose m+1}{m+1 \choose m}$$ times. But to look at it another way: Suppose an element is contained in $$m+2$$ sets, every way to choose $$m$$ sets induces exactly 1 way to undercount it. (Words are failing to express my intuition here. I hope you can grasp that.) The same holds for $$m+3, m+4, \dots, n$$.

I guess there is a clever and clear way of saying that when you properly formulate everything. But it is currently out of my reach.

• Thank you very much! This was certainly helpful. :)
– Shay
Commented Nov 27, 2021 at 16:23

The best teacher for this one is yourself. You have a proof, just not one you like very much yet. Keep working at it, look at some more examples, try to build intuition. Somebody may be able to give you an explanation you like a little better than the last one your heard, but there's no substitute for figuring it out yourself, like you did with the basic case. Try forgetting the formula and reinventing it yourself for $$m = 1$$ or $$m = 2$$ say.

• You're right, of course, that the ideal solution would be for me to play with the concept until I figure it out; the issue was mainly that I hoped to build this intuition while I had to study for five different exams, and it was clear that I couldn't afford to do it during this limited exam prep period, so I was almost prepared to reluctantly settle for "just accepting it" as a temporary solution.
– Shay
Commented Nov 27, 2021 at 16:31
• However, oftentimes, a good explanation from someone who already has a solid intuition can speed this process up, and I was hoping for one such explanation to assist me with obtaining said intuition in time. Also, thank you for your input, it was helpful! :)
– Shay
Commented Nov 27, 2021 at 16:31