Weighted Version of Inclusion-Exclusion Principle.

Question

I am trying to understand the formula $\omega(E_{s}$)=$\sum\limits_{t=s}^{r}(-1)^{t-s}\binom{t}{s}W(t)$, where E$_{s}$={k|f(k)=s} and f is f=$\chi_{N_{2}}+\cdot\cdot+\chi_{N_{r}}$, where $\chi$ is the indicator function. I understand the general inclusion-exclusion principle. But I can't do anything with the weights and the indicator function. Can you give me an example? Thank you very much in advance.

Answer 1

When you have $r$ sets, $N_1,N_2,\dots,N_r$, the usual principle of inclusion exclusion tells you how to count the number of elements which are contained in exactly $0$ of the sets (equivalently, taking complements, it tells you the number of elements in at least one set).

The equation you are referencing generalizes this. For any $s$, it tells you how to count the number of elements appearing in exactly $s$ of the sets.

Here is one example. Suppose $m$ people leave their coats at the coat check-in, but when they leave, the attendant gives each person one of the stored coats randomly. You can ask, what is the probability that no one gets their coat back? Here, the sets are $N_1,N_2,\dots,N_m$, where $N_i$ is the set of permutations where person number $i$ receives their own coat. Note that $|N_1\cap N_2\cap \cdots \cap N_t|=(m-t)!$, since persons $1,\dots,t$ receive their coat, while the other $m-t$ people can be permuted arbitrarily. The usual PIE then tells us that $$ \text{# permutations where 0 people receive their coat}=\sum_{t=0}^m (-1)^t\binom mt (m-t)! $$ OK, but how do we count permutations where exactly $s$ people receive their coat back? This is where your generalized version comes in handy: $$ \text{# permutations where $s$ people receive their coat}=\sum_{t=s}^m (-1)^t\binom ts\binom mt (m-t)! $$ Here are some more examples:

• How many ways are their for $n$ husband/wife pairs to sit around a circular table, alternating by gender, so that there are exactly $k$ adjacent husband wife pairs? Find the number of $n$ husband's placing

• When you distribute balls randomly into bags, what is the probability distribution of the number of empty bags? If I randomly (uniformly) distribute n balls into k bags, what is the distribution of the number of empty bags?

• Calculate the probability distribution describing the number of same suited $AK$ pairs in a hand of $13$ cards.