Chapter 2, Exercise 25 of R. Stanley's "Enumerative Combinatorics" Vol. 1 asserts that
$$ \sum\_{m,n \geq 0} \left(\sum\_{t \geq 0} f\_i(m,n)t^i\right)\frac{x^m}{m!}\frac{y^n}{n!} = e^{-x-y}\sum\_{m,n \geq 0} (1+t)^{mn} \frac{x^m}{m!}\frac{x^n}{n!},$$
where $f\_i(m,n)$ is the number of $m\times n$ $0,1$-matrices with at least one $1$ in every row and every column, and with $i$ total $1$'s.


I know how to prove this, following the method suggested in the exercise of using the principle of inclusion exclusion to get a formula for $\sum\_{t \geq 0} f\_i(m,n)t^i$ and then carrying out some standard but slightly tricky generating function manipulations.


**Question**: Is there a "bijective" proof of this identity? Note that $(1+t)^{mn}$ is evidently the generating function of *all* $m\times n$ $0,1$-matrices (according to number of $1$'s).


I guess it's a little hard to imagine what a bijective proof could be considering the appearance of exponential generating functions and the factor $e^{-x-y}$, but what I really want to know is:


**Question, reformulated**: Is there any more conceptual explanation for this identity? I am especially interested in an explanation for the way that the generating functions $\sum\_{t \geq 0} f\_i(m,n)t^i$ and $(1+t)^{mn}$ for $m\times n$ $0,1$-matrices with/without restrictions enter into the expression.



$0,1$-matrices with $1$ in every row/column vs. all $0,1$-matrices
If you multiply both sides by $e^{x+y}$ there's a simple bijective proof: In a nutshell, every 0-1 matrix consists of a matrix with a 1 in every row and column together with some all-zero rows and columns.


If you restate this in terms of bipartite (or more precisely, bicolored—bipartite with a specified bipartition) graphs you get something more familiar from the point of view of exponential generating functions: every bicolored graph consists of a bicolored graph with no isolated vertices together with a set of isolated vertices.


