4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Ah, okay. Is it something special about two dimensions? For example the analogous statement is not true of $3D$-arrays, right? $\endgroup$
    – Sam Hopkins
    Commented Oct 7, 2021 at 2:47
  • $\begingroup$ No, there's nothing special about two dimensions. The analogous statement will be true for 3D arrays. Think of a 3D 0-1 arrays as tricolored 3-regular hypergraph: you have three vertex sets each a different color, corresponding to the three coordinates, and each 1 of the array corresponds to a triple of vertices, one of each color. Each such hypergraph will be a set of isolated vertices together with a hypergraph without isolated vertices. $\endgroup$
    – Ira Gessel
    Commented Oct 7, 2021 at 3:04
  • $\begingroup$ But I can't really delete a row/column(/pillar) of a 3D array and be left with a 3D array, the way I can in 2D... $\endgroup$
    – Sam Hopkins
    Commented Oct 7, 2021 at 3:05
  • $\begingroup$ By the same reasoning the exponential generating function for (labeled) graphs without isolated vertices is $e^{-x}\sum_{n=0}^\infty 2^{\binom n2} x^n/n!$; these correspond to symmetric 0-1 matrices with 0s on the diagonal and a 1 in every row. (oeis.org/A006129) $\endgroup$
    – Ira Gessel
    Commented Oct 7, 2021 at 3:09
  • 1
    $\begingroup$ You have to delete a 2-dimensional slice. That's what corresponds to a vertex. So the analogous statement for $n$-dimensional arrays will be about arrays in which every $n-1$-dimensional slice has at least one 1. $\endgroup$
    – Ira Gessel
    Commented Oct 7, 2021 at 3:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .