# Spanning forests of bipartite graphs and distinct row/column sums of binary matrices

Let $$F_{m,n}$$ be the set of spanning forests on the complete bipartite graph $$K_{m,n}$$. Let $$S_{m,n} = \{(r(M), c(M)), M \in B_{m,n} \}$$ where $$B_{m,n}$$ is the set of $$m \times n$$ binary matrices and $$r(M), c(M)$$ are the vectors of row sums and column sums of $$M$$, respecitvely. That is, $$S_{m,n}$$ is the set of the distinct row-sum, column-sum pairs of binary matrices. (The term spanning forest here refers to a forest that spans all of the vertices of the given graph; it doesn't have to be a maximal acyclic subgraph.)

Q: Is it true that $$|F_{m,n}| = |S_{m,n}|$$? It is true for $$m,n \leq 4$$. For $$m=n$$ this is OEIS A297077.

There is an obvious mapping from $$F_{m,n} \rightarrow B_{m,n}$$ given by taking the reduced adjacency matrix, so if $$U = \{u_1, \ldots, u_m\}$$, $$V = \{v_1, \ldots, v_m\}$$ are the color categories we set $$M_{ij} = 1$$ if $$v_i \sim u_j$$ in a forest $$F$$, else $$M_{ij} = 0$$. However, this does not help because multiple forests may have the same row and column sums - and not every row-sum, column-sum pair is represented by a forest under this mapping.

The numbers $$|F_{m,n}|$$ are given here:

$$\begin{array}{|c|c|}\hline m\backslash n & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 2 & \\\hline 2 & 4 & 15 \\\hline 3 & 8 & 54 & 328 \\\hline 4 & 16 & 189 & 1856 & 16145 \\\hline 5 & 32 & 648 & 9984 & 129000 & 1475856 \\\hline\end{array}$$

For more see this answer (sum each row.)

• The linked MSE thread calculates $|F_{m,n}|$, but how did you calculate $|S_{m,n}|$ to verify they are the same for $m,n\le 4$? Did you just generate all $2^{mn}$ binary matrices? – antkam May 24 '19 at 19:24
• Yes, I did a brute force count. – Jair Taylor May 24 '19 at 22:32
• Just curious: what made you do the brute force count to find out they're equal? Nothing in the "obvious mapping" would suggest (to me) that they are equal, so it would never have occurred to me to even try. – antkam May 25 '19 at 22:54
• @antkam I was interested in counting forests and found that the relevant OEIS entry only mentioned row-sum / column-sums. – Jair Taylor May 26 '19 at 1:01
• In my Answer, when interpreting $F_{m,n}$, I wrote "In your definition, a spanning forest is any subset $T$ of edges of $K_{2,n}$ which is acyclic." So e.g. the empty $T=\emptyset$ qualifies, and in general nodes can be isolated/unconnected. First of all, is my interpretation correct? Second, if I'm correct, then IMHO your use of the word "spanning" is a little confusing. I understand you probably want to make sure unconnected nodes are still included, and simply saying "forest" might also be confusing in a different way... – antkam May 30 '19 at 12:49

I can prove the conjecture, although I can't give a bijection. I've left up a previous answer which does the case $$m=3$$, since it serves as an example of many of the ideas here.

Here is the key observation:

Theorem: There is a unique array $$f(m,n)$$, for $$m$$ and $$n$$ nonnegative integers, satisfying:

1. $$f(m,0) = f(0,n)=1$$

2. If we fix $$m \geq 1$$, then $$f(m,n)$$ is of the form $$(m+1)^n p_m(n)$$ where $$p_m(x)$$ is a polynomial of degree $$\leq m-1$$.

3. If we fix $$n \geq 1$$, then $$f(m,n)$$ is of the form $$(n+1)^m p_n(m)$$ where $$p_n(x)$$ is a polynomial of degree $$\leq n-1$$.

Uniqueness: Let's suppose that we have already found unique values of $$f(m,n)$$ whenever $$\min(m,n) < k$$. In particular, we know the values of $$f(k,x)$$ and $$f(x,k)$$ for $$0 \leq x \leq k-1$$. This is enough values to uniquely determine a degree $$k-1$$ polynomial, so the values we already know determine the values of $$f(k,x)$$ and $$f(x,k)$$ for all $$x$$.

Existence: The proof of uniqueness gives an algorithm to compute $$f$$. The only potential issue is that $$f(k,k)$$ is determined twice, as a polynomial in its first variable and in its second variable. However, the algorithm is symmetric in $$m$$ and $$n$$, so the two interpolating polynomials coincide. $$\square$$

For example, we have $$f(1,0) = 1 = 2^0 \cdot 1$$ so we must have $$p_1(n)=1$$ and $$f(1,n) = 2^n$$. Similarly, $$f(2,0)=1=2^0 \cdot 1$$ and $$f(2,1) = 4=3^1 \cdot (4/3)$$, so we must have $$p_2(n) = 1+n/3$$ and $$f(2,n) = 3^n(1+n/3) = 3^{n-1} (n+3)$$. Using this algorithm, I computed $$f(m,n)$$ for $$0 \leq m,n \leq 10$$. Here is the data, and some Mathematica code, if you'd like to play with it.

f[m_, n_] := f[m, n] =
If[m == 0 || n == 0, 1,
If[m <= n,
(m + 1)^n * InterpolatingPolynomial[Table[{k, f[m, k]/(m + 1)^k}, {k, 0, m - 1}], x] /. x -> n,
(n + 1)^m * InterpolatingPolynomial[Table[{k, f[k, n]/(n + 1)^k}, {k, 0, n - 1}], x] /. x -> m]]


Values of $$f(m,n)$$ for $$0 \leq m,n \leq 10$$.

1,1,1,1,1,1,1,1,1,1,1
1,2,4,8,16,32,64,128,256,512,1024
1,4,15,54,189,648,2187,7290,24057,78732,255879
1,8,54,328,1856,9984,51712,260096,1277952,6160384,29229056
1,16,189,1856,16145,129000,968125,6925000,47690625,318500000,2073828125
1,32,648,9984,129000,1475856,15450912,151201728,1403288064,12479546880,107152782336
1,64,2187,51712,968125,15450912,219682183,2862173104,34828543449,401200569280,4418300077219
1,128,7290,260096,6925000,151201728,2862173104,48658878080,760774053888,11122973573120,153936323805184
1,256,24057,1277952,47690625,1403288064,34828543449,760774053888,15047189968833,274908280855680,4707029151392121
1,512,78732,6160384,318500000,12479546880,401200569280,11122973573120,274908280855680,6199170628499200,129708290461760000
1,1024,255879,29229056,2073828125,107152782336,4418300077219,153936323805184,4707029151392121,129708290461760000,3283463201858585471


So, we can prove the conjecture by showing that both $$F_{m,n}$$ and $$S_{m,n}$$ obey conditions 1, 2 and 3. For condition 1, we can just define $$S_{m,0}$$, $$S_{0,n}$$, $$F_{m,0}$$, and $$F_{0,n}$$ to be singletons (and I claim this is actually the most natural definition); then we just need to check that our verification of polynomiality goes all the way down to the zero case.

Since conditions 2 and 3 are symmetric, and the definitions of $$F_{m,n}$$ and $$S_{m,n}$$ are symmetric, we just check condition $$2$$.

Verification of condition 2 for forests: Let $$A_{m,b}$$ be the set of isomorphism classes of bicolored forests whose white vertices are labeled $$\{1,2,\ldots,m \}$$ and which have $$b$$ black vertices, each of degree $$\geq 2$$. We claim that $$|F_{m,n}| = \sum_b |A_{m,b}| n(n-1)(n-2) \cdots (n-b+1) (m+1)^{n-b} . \qquad (1)$$

Proof: Take a forest in $$F_{m,n}$$, with the $$m$$ vertices colored white and the $$n$$ vertices colored black. Delete all black vertices of degree $$0$$ and $$1$$ and forget the numbering of the remaining black vertices. This gives a forest in $$A_{m,b}$$. To undo this process, we first must take the $$b$$ black vertices and decide which of the $$n$$ vertices of $$K_{m,n}$$ they will be; there are $$n(n-1)(n-2) \cdots (n-b+1)$$ ways to do this. (We used that trees in $$A_{m,b}$$ have no automorphisms.) Then we must take the $$n-b$$ remaining black vertices and either join them to one of the $$m$$ white vertices or leave them unconnected; there $$(m+1)^{n-b}$$ ways to do this.

Formula (1) is clearly $$(m+1)^n$$ times a polynomial, it remains to check that the polynomial has degree at most $$m-1$$. We must check that $$A_{m,b}$$ is empty if $$b \geq m$$. Indeed, since every black vertex has degree at least $$2$$, a forest in $$A_{m,b}$$ has at least $$2b$$ edges. But, since it is a forest, it also has at most $$m+b-1$$ vertices. So $$2b \leq m+b-1$$ and $$b \leq m-1$$. $$\square$$

Verification of condition 2 for margins of $$(0,1)$$ matrices: Consider a vector $$C = (C_1, \ldots, C_n) \in \{ 0,1,\ldots, m \}^n$$ of columns sums, and consider how many row sums $$(R_1, \ldots, R_m)$$ are compatible with it. Let $$c_j = \# \{ k : C_k = j \}$$, so $$c_0+c_1+\cdots + c_m=n$$.

By the Gale-Ryser theorem, $$(R_1, \ldots, R_m)$$ is compatible with $$(c_0, \cdots, c_m)$$ if and only if $$\sum R_i = \sum j c_j$$ and, for all index sets $$1 \leq i_1 < i_2 < \cdots < i_k \leq m$$, we have $$R_{i_1} + R_{i_2} + \cdots + R_{i_k} \leq \sum_j \min(j,k) c_j .$$ This is the defining list of inequalities of the permutahedron, so this condition can alternately be stated as saying that $$(R_1, \ldots, R_m)$$ is in the convex hull of the $$m!$$ permutations of $$(c_1+c_2+\cdots+c_m, c_2+\cdots + c_m, \cdots, c_{m-1}+c_m, c_m)$$.

By Theorem 11.3 of Postnikov's Permutohedra, associahedra, and beyond, the number of such $$(R_1, \ldots, R_m)$$ is a polynomial $$g_m(c_0,c_1, \ldots, c_m)$$ in the $$c_j$$, of degree $$m-1$$. So $$|S_{m,n}| = \sum_{c_0+\cdots + c_m=n} \frac{n!}{c_0! c_1! \cdots c_m!} \ g_m(c_0,c_1, \ldots, c_m). \qquad (2)$$ Let $$\partial_j$$ be $$\tfrac{\partial}{\partial x_j}$$. There is some polynomial $$h_m$$ in the $$\partial_j$$, of degree $$m-1$$, such that $$\left. h_m(\partial_0, \ldots, \partial_m) \left( x_0^{c_0} \cdots x_m^{c_m} \right) \right|_{(1,1,\ldots,1)} = g_m(c_1, \ldots, c_m). \qquad (3)$$ Combining (2), (3) and the binomial expansion of $$(x_0+x_1+\cdots+x_m)^n$$, we obtain $$|S_{m,n}| = \left. h_m(\partial_0, \ldots, \partial_m) \left( x_0+x_1+\cdots+x_m \right)^n \right|_{(1,1,\ldots,1)} . \qquad (4)$$ Let $$h_m(t,t,\ldots,t) = \sum_{k=0}^{m-1} h_{m,k} t^k$$. Then $$(4)$$ is $$\sum_{k=0}^{m-1} h_{m,k} n(n-1)(n-2) \cdots (n-k+1) (m+1)^{n-k}$$, which is a polynomial of the desired form. $$\square$$

• Very cool! I think you need another index on your coefficients $c_k$ (say $c_{m,k}$). Then you've shown $c_{m,k} = |A_{m, k}|$ which is interesting as well. I'd be curious to see if this could be generalized more - e.g., to forests with a specified number of components. But I don't know what the appropriate statistic on row-sums/column-sums would be. – Jair Taylor Jun 2 '19 at 21:16
• @JairTaylor Nice observation. Your comment made me realize I had used $c_j$ to mean two things, so I changed the second one to $h_{m,k}$; your observation then is that I have shown $h_{m,k} = |A_{m,k}|$. – David E Speyer Aug 27 '19 at 15:38

This conjectured equivalence (if true) is still amazing to me. However, here is a baby step: The conjecture is indeed true for $$m=2$$. Perhaps someone else will find this useful as a base for generalization.

Claim: $$|F_{2,n}| = |S_{2,n}|$$ for all $$n$$

First, lets consider $$F_{2,n}$$. In your definition, a spanning forest is any subset $$T$$ of edges of $$K_{2,n}$$ which is acyclic. Let $$u,v$$ be the two nodes on the $$m=2$$ side, and let $$S(u)$$ be the neighbors of $$u$$, i.e. the subset of nodes (on the $$n$$-node side) which $$u$$ is connected to in $$T$$. Similarly for $$S(v)$$.

Next, note that $$T$$ contains a cycle iff $$S = S(u) \cap S(v)$$ contains $$2$$ nodes (or more). So, $$F_{2,n}$$ can be counted by counting all cases where $$S$$ contains $$0$$ or $$1$$ node.

• $$|S|=0$$ case: Each of $$n$$ nodes can be connected to $$u$$, or to $$v$$, or to neither. Total no. $$= 3^n$$.

• $$|S|=1$$ case: There are $$n$$ ways to pick the unique $$w \in S$$. After that, each of the remaining $$n-1$$ nodes can be connected to $$u$$, or to $$v$$, or to neither. Total no. $$= n\, 3^{n-1}$$

• Summing up, $$|F_{2,n}| = 3^n + n \,3^{n-1} = 3^{n-1} (3+n),$$ which matches your table.

Second, lets consider $$S_{2,n}$$. There are $$n$$ column sums, each of which can be $$0, 1, 2$$. Let $$x,y,z$$ be the number of columns whose sum $$=0, 1, 2$$ respectively. The columns whose sum $$=0$$ or $$2$$ dictate their elements. In the $$y$$ columns whose sum $$=1$$, the number of $$1$$s in the top row can be any integer $$\in [0,y]$$, and so the top row sum can be any integer $$\in [z,z+y]$$, and in short there are $$(y+1)$$ possibilities. Obviously, once the top row sum is known that determines the bottom row sum $$= (y+2z) \,-$$ top row sum.

So $$S_{2,n}$$ can be counted by (i) summing over all possible $$y$$, and for each $$y$$: (ii) picking the $$y$$ columns whose sum $$=1$$, and (iii) for the remaining $$n-y=x+z$$ columns assign them $$0$$ or $$2$$ arbitrarily. I.e.:

$$|S_{2,n}| = \sum_{y=0}^n (y+1) {n \choose y} 2^{n-y}$$

This can be evaluated many ways but my favorite is to recognize a slightly transformed sum as an explicit formula for the expected value of a Binomial random variable:

\begin{align} |S_{2,n}| &= \sum_{y=0}^n (y+1) {n \choose y} 2^{n-y} \\ &= 3^n \times \sum_{y=0}^n (1+y) {n \choose y} (\frac13)^y (\frac23)^{n-y} \\ &= 3^n \times \mathbb{E}[1 + Bin(n, \frac13)] \\ &= 3^n (1 + {n \over 3}) = 3^{n-1} (3 + n) = |F_{2,n}| & QED \end{align}

As I said, this is a baby step only. The key step in $$F_{2,n}$$ is that $$T$$ has a cycle iff $$|S| \ge 2$$, and the key step in $$S_{2,n}$$ is that the $$y$$ ones can be all in the top row or all in the bottom row or anywhere in between, for $$(1+y)$$ possibilities. These key steps make the counting easy. However, as far as I can see, neither key step has any easy way to generalize to $$m=3$$, let alone arbitrary $$m$$. (E.g. for $$m=3$$, a cycle in $$T$$ can involve $$2$$ or $$3$$ nodes on the $$m=3$$ side, and I don't know any good way to count that.)

• Nice start. I would like to see a bijective proof. I wonder if, in general, if $m$ is fixed, $F_{m,n}$ has a rational generating function. – Jair Taylor May 30 '19 at 19:32
• I would like to see a bijective proof even just for $m=2$, instead of this algebraic mess. Also, I am no good at GFs, but in this case, I couldn't even find nice recursions for $F$ or $S$. Do you have recursions for either of them? – antkam May 30 '19 at 19:54

I have a brute force proof that, for $$m=3$$, both counts are $$4^{n - 2} (3 n^2 + 13 n + 16)$$. It would be possible to extend this method for any fixed $$m$$. I'll write it up for $$m=3$$ in the hope it gives insight. As you'll see, many steps look the same on both sides, but I can't figure out how to give a general proof.

Counting margins of $$3 \times n$$ binary matrices Consider a vector $$C \in \{ 0,1,2,3 \}^n$$ of column sums. Let $$C$$ have $$c_j$$ entries equal to $$j$$ (so $$c_0+c_1+c_2+c_3=n$$). Let's consider how many row sums $$(R_1, R_2, R_3)$$ are compatible with $$C$$. By the Gale-Ryser theorem, these are the vectors with $$R_1+R_2+R_3 = c_1+2c_2+3c_3$$, $$\min(R_1+R_2, R_1+R_3, R_2+R_3) \geq c_2+2c_3$$ and $$\min(R_1, R_2, R_3)\geq c_3$$. Geometrically, this is the lattice points in a hexagon whose vertices are the permutations of $$(c_1+c_2+c_3, c_2+c_3, c_3)$$. I computed that the number of lattice points in this hexagon is $$\binom{c_1}{2} + 2 c_1 c_2 + \binom{c_2}{2} + 2 c_1 + 2 c_2 + 1.$$

The generating function for $$\sum_C x_0^{c_0} x_1^{c_1} x_2^{c_2} x_3^{c_3}$$ is $$(x_0+x_1+x_2+x_3)^n$$. Let $$\partial_j$$ be differentiation with respect to $$x_j$$. Let $$D$$ be the differential operator $$\tfrac{1}{2} \partial_1^2 + 2 \partial_1 \partial_2+\tfrac{1}{2} \partial_2^2 + 2 \partial_1 + 2 \partial_2 + 1.$$ Then $$D$$ applied to the monomial $$x_0^{c_0} x_1^{c_1} x_2^{c_2} x_3^{c_3}$$, and evaluated at $$(1,1,1,1)$$, gives $$\binom{c_1}{2} + 2 c_1 c_2 + \binom{c_2}{2} + 2 c_1 + 2 c_2 + 1$$. So the number of pairs $$(C,R)$$ is $$D (x_0+x_1+x_2+x_3)^n$$ evaluated at $$(1,1,1,1)$$.

This gives $$3 n(n-1) 4^{n-2} + 4 n 4^{n-1} + 4^n = 4^{n - 2} (3 n^2 + 13 n + 16)$$.

Counting forests Given a forest on $$3 \times n$$, define a sequence $$(v_1, v_2, \ldots, v_n)$$ in $$\{ 0,1,2,3 \}^n$$ by saying that $$v_j$$ is $$0$$ if vertex $$j$$ has degree $$0$$, and otherwise $$v_j$$ is the least neighbor of $$j$$. Let $$c_j$$ be the number of $$v_j$$'s equal to $$j$$.

The generating function for the $$(c_0, c_1, c_2, c_3)$$ sequences is $$(x_0+x_1+x_2+x_3)^n$$ (again!). We count how many forests give rise to each $$(c_0, c_1, c_2, c_3)$$, by listing all possiblilities.

One vertex joined to $$(1,2)$$ and another joined to $$(1,3)$$ This can happen in $$c_1 (c_1-1)$$ ways.

One vertex joined to $$(1,2)$$ and another joined to $$(2,3)$$ This can happen in $$c_1 c_2$$ ways.

One vertex joined to $$(1,3)$$ and another joined to $$(2,3)$$ This can happen in $$c_1 c_2$$ ways.

One vertex joined to $$(1,2,3)$$ This can happen in $$c_1$$ ways.

One vertex joined to $$(1,2)$$ This can happen in $$c_1$$ ways.

One vertex joined to $$(1,3)$$ This can happen in $$c_1$$ ways.

One vertex joined to $$(2,3)$$ This can happen in $$c_2$$ ways.

None of the $$n$$-vertices joined to more than one neighbor This can happen in $$1$$ way.

So, this time, we want to sum up $$c_1 (c_1-1) + 2 c_1 c_2 + 3 c_1 + c_2 +1.$$ The corresponding differential operator is $$E=\partial_1^2 + 2 \partial_1 \partial_2 + 3 \partial_1 + \partial_2+1.$$

The differential operators are different, but once again I get $$3 n(n-1) 4^{n-2} + 4 n 4^{n-1} + 4^n$$ at the end of the day.

A thought for the future Why do the differential operators $$\tfrac{1}{2} \partial_1^2 + 2 \partial_1 \partial_2+\tfrac{1}{2} \partial_2^2 + 2 \partial_1 + 2 \partial_2 + 1$$ and $$\partial_1^2 + 2 \partial_1 \partial_2 + 3 \partial_1 + \partial_2+1$$ give the same thing when applied to $$(x_0+x_1+x_2+x_3)^n$$? Because $$(x_0+x_1+x_2+x_3)^n$$ is solely a function of $$z:=x_0+x_1+x_2+x_3$$, so all the $$\partial_j$$'s evaluate to $$\tfrac{d}{dz}$$. Writing $$\partial$$ for $$\tfrac{d}{dz}$$, both operators are $$3 \partial^2 + 4 \partial + 1$$. Any hope to generalize this?

• Nice. I was not aware of Gale-Ryser. If I understand correctly, this could give a method of verifying the conjecture for any fixed $m$ by counting lattice points of appropriate polytopes (to count $S_{m,n}$) and enumerating all possible families of subsets of $[m]$ sharing neighbors (to count $F_{m,n}$), both reducing to finite counting problems. Still, it seems like this problem is crying out for an explicit bijection. – Jair Taylor Jun 1 '19 at 13:43