Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

(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?

share|improve this question
    
Did you leave out the word "symmetric" on purpose? –  Brendan McKay Feb 23 at 23:38

2 Answers 2

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.

share|improve this answer

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

share|improve this answer
    
Interesting. I would've said that X_{4,n} is the number of labeled directed graphs such that each vertex has indegree and outdegree 4 (is this what "regular" means for directed graphs?) and with no multiple edges or self-loops. –  Qiaochu Yuan Jan 18 '10 at 13:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.