6
$\begingroup$

What is the number of $n \times n$ binary matrices with row and column sums 2 and with only zeros on the diagonal? This simple problem must have been treated somewhere, but I couldn't find any reference, even an OEIS entry. Among many aspects of this problem, I mostly care about the recurrence formula satisfied by enumeration result indexed by $n$. Note that this recurrence exists, as it can be shown that the sequence is P-recursive.

The case where the row and column sums all equal to 1 is the familiar problem of counting permutations with no fixed points. If the matrix is constrained to be symmetric, the result is given by the OEIS sequence A001205. It turns out that the non-symmetric case is quite more difficult.

$\endgroup$
1
  • 1
    $\begingroup$ In general, the number of $n \times n$ matrices with coefficients in $\mathbb{N}$ and with all row and column sums equal to $r$ is the number of lattice points in the $r$th dilate of the Birkhoff polytope. Hence, these kind of problems are studied often from the point of view of Ehrhart theory. Your variant has two changes: you are looking at binary matrices (so in particular the value $2$ is not allowed), and you want $0$'s on the diagonal. Still, the literature on the Ehrhart theory of the Birkhoff polytope and Stanley’s solution of the "Anand-Dumir-Gupta conjecture" may be a place to start. $\endgroup$ Commented May 18 at 23:44

1 Answer 1

7
$\begingroup$

This is OEIS A007107.

Number of labeled $2$-regular digraphs with $n$ nodes

Or number of $n\times n$ matrices with exactly two $1$'s in each row and column which are not in the main diagonal, other entries $0$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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