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.

3more comments