Skip to main content
1 of 3
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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!~.$$

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147