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.

Improve this question
$\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$
    – Sam Hopkins
    Commented May 18 at 23:44

1 Answer 1

Reset to default
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$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .