How many n×n (0,1)-matrices with row/column sum 4 and trace 0 are there?

Question

(asked by Shanzhen Gao, shanzhengao at yahoo.com, on the Q&A board at JMM)

Is there a closed formula for the number of n×n (0,1)-matrices with column sum 4, row sum 4, and trace 0?

Answer 1

A formula (due to Musiker and Odama) for the number of $n\times n$ (0,1)-matrices with line sum 4 appears on page 5 of the first link at http://www.mtholyoke.edu/courses/gcobb/REU_MCMC/papers.html. The technique can easily be modified to give a formula for the trace 0 case.

Answer 2

This is somewhat of an ill-posed question, since "closed" is a very vague term. See: H. S. Wilf, `What is an answer?', Amer. Math. Monthly 89 (1982), 289-292.

A $k \times n$ Latin rectangle is an $k \times n$ matrix with symbols from $\mathbb{Z}_n$ in which each symbol occurs exactly once in each row and at most once in each column. A Latin rectangle is called normalised if its first row is $(0,1,\ldots,n-1)$. Given a $5 \times n$ normalised Latin rectangle $L=(l_{ij})$ we can construct a $n \times n$ $(0,1)$-matrix $T=(t_{ij})$ by setting $t_{ij}=1$ if symbol $j$ appears in column $i$ of $L$ (and $t_{ij}=0$ otherwise). We see that every row and every column of $T$ contains exactly $5$ copies of the symbol $1$. Moreover, since $L$ is normalised, $t_{ii}=1$ for all $i \in \mathbb{Z}_n$. Let $T'$ be formed from $T$ by setting main diagonal of $T$ to $(0,0,\ldots,0)$. Then $T'$ contains row sum $4$ and column sum $4$ and trace $0$.

Let $X_{4,n}$ be the number of $n \times n$ $(0,1)$-matrices with column sum 4 and row sum 4 and trace $0$. It is a well-known result that each $(0,1)$-matrix counted by $X_{4,n}$ can be formed as $T'$ for some normalised $5 \times n$ Latin rectangle (from Hall's Marriage Theorem). We conclude that $X_{4,n} \leq K_{5,n}$, where $K_{5,n}$ is the number of normalised $5 \times n$ Latin rectangles. Erdos and Kaplansky showed that $K_{5,n} \sim n!^4 e^{-10}$ (although you can expect $X_{4,n}$ to be much less than this).

There are several published formulae for the number of Latin rectangles (in fact, I have a paper on this topic). There's a good chance that modifying one of these formulae would yield a formula for $X_{4,n}$. One good example is by Doyle: http://arxiv.org/abs/math/0703896.

In addition, there is a easy graph theoretic interpretation of $X_{4,n}$. Let $G$ be the complete bipartite graph with bipartition $\{v_1,v_2,\ldots,v_n\} \cup \{u_1,u_2,\ldots,u_n\}$. Then $X_{4,n}$ is the number of $4$-regular subgraphs $H$ of $G$ minus the one-factor $\{v_i u_i\}_{1 \leq i \leq n}$ (on the same vertex set as $G$). Given such a subgraph $H$, let $X=(x_{ij})$ be defined by $x_{ij}=1$ if $v_i$ is adjacent to $u_j$ in $H$.