2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – darij grinberg Oct 22 '18 at 2:40
  • $\begingroup$ What do you mean by “... and a given number $k$ of $1$-less columns”? $\endgroup$ – J.Summer Oct 22 '18 at 2:47
  • $\begingroup$ 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. $\endgroup$ – darij grinberg Oct 22 '18 at 3:05
  • $\begingroup$ Thank you! I have figured it out. $\endgroup$ – J.Summer Oct 23 '18 at 1:24
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.