# A strange sum over bipartite graphs

While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone sees a nice interpretation. The sum is over all simple bipartite graphs $G$ with $n$ vertices on each side, the product is over all $2n$ vertices $v$ of $G$ and $d_G(v)$ is the degree of vertex $v$ in graph $G$. $$\sum_{G\subseteq K_{n,n}} ~ \prod_{v\in V(G)} (n-2d_G(v)) = 2^{n^2}n!~.\kern 3cm (1)$$

Addition 1, proof. Consider $n^2$ commuting indeterminates $\{x_{ij}\}_{i,j=1\ldots n}$. The polynomial $$P(\boldsymbol{x}) = \prod_{i=1}^n \sum_{j=1}^n x_{i,j} \times \prod_{j=1}^n \sum_{i=1}^n x_{i,j}.$$ has terms with each variable having power 0, 1 or 2. Consider the total coefficient $C~$ of the terms with only even powers. One way is to sum each variable over $\pm 1$, which makes the terms we don't want cancel out and the others get multiplied by $2^{n^2}$. This gives (1), interpreting $G$ as the bipartite graph whose edges are the variables with value $-1$. Alternatively, note that each term has total degree $2n$ and the only possible such term with even degrees is $\prod_{i=1}^n x_{i,\sigma(i)}^2$ for some permutation $\sigma$. This shows $C=n!~$.

Addition 2, generalisation. Define the numbers $$\rho(n,k,d) = \sum_{j\ge 0} (-1)^j \binom{d}{j} \binom{n-d}{k-j}.$$ Let $k_1,\ldots,k_{2n}$ be a sequence of nonnegative integers. Then $$\sum_{G\subseteq K_{n,n}} ~ \prod_{v\in V(G)} \rho(n,k_v,d_G(v)) = 2^{n^2} B(\boldsymbol{k}),$$ where $B(\boldsymbol{k})$ is the number of simple bipartite graphs with vertex $v$ having degree $k_v$ for all $v$. The case (1) follows from $\rho(n,1,d)=n-2d$. The proof of the general case is similar.

• A little playing with your sum shows that if you replace the appearance of n in the left hand side of your equation by a variable t, the right hand side becomes $2^{n^2}n!L_n(-(t-n)^2)$, with $L_n$ the $n$th Laguerre polynomial. Maybe this has a meaning? $${}$$ Extra points for introducing a $q$ somewhere in the left hand side and getting $q$-Laguerre polynomials on the right hand side! – Mariano Suárez-Álvarez Mar 5 '12 at 9:34
• An unsuccessful approach is to weigh each summand by the number $e(G)$ of edges in $G$: we get $$\sum_{G\subseteq K_{n,n}} ~ q^{e(g)}\prod_{v\in V(G)} (t-2d_G(v)) = 4^n n! q^n (q+1)^{n^2-2 n} L_n\left(-\frac{((q+1) t-2 n q)^2}{4 q}\right).$$ – Mariano Suárez-Álvarez Mar 5 '12 at 10:02
• (It is cute, though, how $2n$ of the factors of $2$ in the formula without the $q$s stay $2$s, while the other $n^2-2n$ become $(1+q)$s...) – Mariano Suárez-Álvarez Mar 5 '12 at 10:25
• Out of curiosity, what is the average value of the product (I don't have the number of summands readily available, and you (@Brendan) probably do...) – Igor Rivin Mar 5 '12 at 17:53
• So, the statement is that the expected value of the product is $n!.$ I find it really hard to believe that there is not a a simple way to see this (on the other hand, I am not seeing it right now :() – Igor Rivin Mar 5 '12 at 20:53

I'm not sure if this is the right interpretation or not...it may really just be another way of encoding the generating function argument. Let $H$ be a random bipartite graph where every edge appears independently with probability $1/2$. Then the left hand side is $$2^{n^2} E \left(\prod_v f(v) \right),$$ where $f(v)$ is equal to $\sum_u x(u,v)$ and $x(u,v)$ is $1$ if an edge is not present, $-1$ if an edge is present. Expanding out the product and using linearity of expectation, we can write this as
$$2^{n^2} \sum_{\sigma} E \left(\prod_{v} x(v,\sigma(v))\right)$$ Where $\sigma$ consists of all mappings taking each vertex to a vertex on the opposite side.
Any $\sigma$ for which some edge $(v,\sigma(v))$ appears only once has $0$ expectation due to independence. The $\sigma$ for which every edge appears for both of its endpoints correspond to matchings between the left and right side, of which there are $n!$. (This last observation corresponds to the fact that the expected square of the permanent of an $n \times n$ random Bernoulli matrix is $n!$...I think it goes at least back to Turan).