Application of the Principle of Inclusion-Exclusion

Question

This is problem 25 from chapter 2, Stanley’s Enumerative Combinatorics Volume 1.

$$ \begin{align} \mbox{(a) } &\text{ [2]* Let $ f_i(m, n) $ be the number of $ m \times n $ matrices of $ 0 $'s and $ 1 $'s with at least } \\ &\text{ one $ 1 $ in every row and column, and with a total of $ i $ $ 1 $'s. Use the Principle of } \\ &\text{ Inclusion-Exclusion to show that } \end{align} $$

$$ \sum_i f_i(m, n)t^i = \sum_{k = 0}^n (-1)^k \binom{n}{k} ((1 + t)^{n - k} - 1)^m \text{.} \qquad \qquad \mbox{(2.54)}$$

I’m quite confused here because I don’t know how to compare this to the Principle of Inclusion-Exclusion. Should I first expand the RHS to get the coefficient of $t^i$? I was trying to get something like $$f_{=}(\phi)=\sum_{k=0}^n \sum_{y\subset\{1,...,n\},|y|=k}(-1)^k f_{\geq}(y).$$But that just doesn’t make sense here.

Any idea? Thank you!

Answer 1

Here's how I thought about this problem:

1. $\binom{n}{k}$ represents choosing $k$ things from a set of $n$ things. There's only one set of $n$ things in the picture, so that must mean choosing $k$ columns of the matrix.

2. $(1 + t)^{n - k}$ is the generating function for subsets of $n - k$.

3. Presumably the $n - k$ are the columns not chosen in step 1.

4. $(1 + t)^{n - k} - 1$ is the generating function for non-empty subsets of $n - k$.

5. $((1 + t)^{n - k} - 1)^m$ is the generating function for $m$ (ordered) non-empty subsets of $n - k$.

6. Specifically $[t^i]((1 + t)^{n - k} - 1)^m$ counts the number of tuples $(A_1,\dots,A_m)$ where each $A_l$ is a non-empty subset of size $n - k$ and $|A_1| + \dots + |A_m| = i$.

Now see if you can put this all together into a proof. (Hint: what is $A_l$ in the matrices enumerated on the left hand side?)