You're already familiar with the basic Principle of Inclusion-Exclusion (PIE), which helps count the elements in the union of several sets. It's a way to handle overcounting by systematically adding and subtracting the sizes of intersections. Now, we'll push this principle further to solve more complex problems.

What if we don't want to count elements that have at least one property, but elements that have exactly a certain number of properties? This requires a more nuanced version of the formula.

This formula might look intimidating, but it's a powerful tool for precision counting. The binomial coefficient $\binom{j}{k}$ accounts for the fact that an element with $j$ properties is counted in $N_j$ once, but it's also counted in the calculations for $N_{j+1}, N_{j+2}$, and so on. This formula corrects for all the layers of over- and under-counting to isolate just the elements with exactly $k$ properties.

A clean way to prove the generalized PIE is by using indicator functions. An indicator function for a set $A$ is a function that tells you whether an element is in the set or not.

Let's consider an element $x$ from our universal set. Let $P_1, P_2, \dots, P_n$ be the properties, and let $A_i$ be the set of elements with property $P_i$. Suppose $x$ has exactly $m$ of these properties. We want to show that its contribution to the right side of the generalized PIE formula is 1 if $m=k$ and 0 otherwise.

The number of times $x$ is counted in $N_j$ is $\binom{m}{j}$, since we must choose $j$ properties from the $m$ properties that $x$ possesses. If $j > m$, this value is 0. So, the total count for element $x$ in the sum is:

Using the binomial identity $\binom{m}{j}\binom{j}{k} = \binom{m}{k}\binom{m-k}{j-k}$, we can rewrite the sum:

Let's make a substitution $s = j-k$. The sum becomes $\sum_{s=0}^{m-k} (-1)^{s} \binom{m-k}{s}$. By the binomial theorem, this sum is equal to $(1-1)^{m-k}$, which is 0 if $m-k > 0$ (i.e., $m > k$) and 1 if $m-k = 0$ (i.e., $m=k$).

Therefore, the element $x$ is counted once if it has exactly $k$ properties ($m=k$) and zero times otherwise. Summing over all elements proves the generalized PIE formula.

One of the classic applications of PIE is counting the number of surjective (or "onto") functions from one finite set to another. A function $f: A \to B$ is surjective if every element in the codomain $B$ is mapped to by at least one element in the domain $A$. Let's say $|A|=m$ and $|B|=n$.

The total number of functions from $A$ to $B$ is $n^m$, since each of the $m$ elements in $A$ can be mapped to any of the $n$ elements in $B$. We want to subtract the functions that are not surjective.

Let's define our properties. Let $P_i$ be the property that the element $b_i \in B$ is not in the image of the function. We want to find the number of functions with exactly 0 of these properties.

Let's calculate $N_j$, the sum of the sizes of all $j$-intersections. An intersection of $j$ sets corresponds to functions that miss at least $j$ specific elements from the codomain $B$. The number of ways to choose these $j$ elements is $\binom{n}{j}$. For each such choice, the number of functions from $A$ to the remaining $n-j$ elements of $B$ is $(n-j)^m$.

So, $N_j = \binom{n}{j}(n-j)^m$.

Now we can plug this into the generalized PIE formula with $k=0$:

This result is closely related to Stirling numbers of the second kind, often denoted $S(m,n)$ or $\left\{ \begin{matrix} m \\ n \end{matrix} \right\}$, which count the number of ways to partition a set of $m$ elements into $n$ non-empty subsets. The number of surjections is $n! \cdot S(m,n)$.

The "problem of the households" is a famous combinatorial problem: In how many ways can $n$ married couples be seated at a round table such that men and women alternate, and no one sits next to their spouse?

First, let's seat the women. There are $(n-1)!$ ways to seat them around a round table. Once they are seated, there are $n$ empty chairs between them for the men. Let's label the women $W_1, \dots, W_n$ in clockwise order. This fixes the positions. Now there are $n!$ ways to seat the men in the empty chairs. The total number of arrangements with alternating genders is $(n-1)! \times n!$.

Now we apply PIE to subtract the arrangements where at least one husband sits next to his wife. A husband $H_i$ can sit next to his wife $W_i$ in two ways: on her left or on her right. Let $P_i$ be the property that husband $H_i$ sits next to his wife $W_i$.

The calculation for $N_j$ becomes quite complex because the choices of which couples sit together are not independent. For example, if $H_1$ sits next to $W_1$ and $H_2$ sits next to $W_2$, the available seats for other husbands are affected. This problem requires a more careful application of PIE, often involving recurrence relations or rook polynomials, but the core idea remains the same: define properties, calculate the size of intersections, and use an alternating sum to find the final count.

These advanced applications show how the simple idea of adding and subtracting can be extended to solve highly constrained counting problems. By carefully defining properties and applying the generalized formula, we can isolate exactly the arrangements we want to count.