# Application of the Principle of Inclusion-Exclusion

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!

• Don't expand anything; that would give you a neat proof but not the one using Inclusion-Exclusion. Instead, count these matrices by first counting all $m\times n$-matrices of $0$'s and $1$'s with at least one $1$ in each row and a given number $k$ of $1$-less columns. (Or maybe switch rows and columns.) – darij grinberg Oct 22 '18 at 2:40
• What do you mean by “... and a given number $k$ of $1$-less columns”? – J.Summer Oct 22 '18 at 2:47
• Actually, a given $k$-element set of $1$-less columns. You fix $k$ distinct elements of $\left\{1,2,\ldots,n\right\}$ and require that the corresponding $k$ columns of your matrix are all-$0$s. – darij grinberg Oct 22 '18 at 3:05
• Thank you! I have figured it out. – J.Summer Oct 23 '18 at 1:24

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?)