Number of all different $n\times n$ matrices where sum of rows and columns is $3$

Question

For a given positive integer $n$, I need to learn the number of $n\times n$ matrices of nonnegative integers with the following restrictions:

1. The sum of each row and column is equal to $3$.
2. Two matrices are considered equal if one can be obtained by permuting rows and/or columns.

For example, for $n=2$ there are two different matrices as follows:

$$M_1=\begin{pmatrix} 1&2\\2&1 \end{pmatrix},\qquad M_2=\begin{pmatrix} 3&0\\0&3 \end{pmatrix}.$$

For $n=3$ there are five different matrices as follows:

$$\begin{pmatrix} 1&1&1\\1&1&1\\1&1&1 \end{pmatrix},\quad \begin{pmatrix} 0&1&2\\1&2&0\\2&0&1 \end{pmatrix}, \quad \begin{pmatrix} 0&1&2\\1&1&1\\2&1&0 \end{pmatrix}, \quad \begin{pmatrix} 1&2&0\\2&1&0\\0&0&3 \end{pmatrix}, \quad \begin{pmatrix} 3&0&0\\0&3&0\\0&0&3 \end{pmatrix}.$$

Answer 1

http://oeis.org/A001501 has an enumeration of binary matrices with row and column sums equal to 3. If n is the order of the matrix, the count grows like n^{3n}. You want classes up to row and column permutations, so your number will grow like n^n.

There are some details to handle, but most of your cases reduce to the following. Such a matrix will be equivalent to one with t 3's on the diagonal, s 2x2 diagonal blocks with 2's and 1's, r more 2's on the diagonal with parallel offset diagonals having 1's, and a remaining block of size qxq with q=n-(t+2s+r), and this block is like one of your matrices but it is binary, and unless r is small you can arrange r zeros on the upper diagonal. When you flip those r diagonal entries from 0 to 1, the qxq block is like one of the matrices enumerated by the OEIS sequence above. So an upper bound will be of order n^{n+3} or smaller. A professional combinatorialist can tighten up the bound for you.

Gerhard "Doesn't Need To Be Professional" Paseman, 2016.10.11.

Answer 2

This problem was solved by Ron Read in his PhD thesis (University of London, 1958). Without requirement 2 there is a summation which isn't too horrible. With requirement 2 added as well, Read's solution needs the cycle index polynomial of a group and you could reasonably call it a solution in principle.

The problem is easier to handle in the asymptotic sense. Without requirement 2, the number is asymptotically $$ \frac{(3n)!}{6^{2n}}\exp\Bigl(2 - \frac{2}{9n} + O(n^{-2})\Bigr),$$ see this paper.

With requirement 2, counting equivalence classes, the key thing to note is that asymptotically almost all of them have only trivial symmetry group, so asymptotically you can divide by $(n!)^2$. See this paper.

For small sizes, starting with $n=1$, I get 1, 2, 5, 12, 31, 103, 383, 1731, 9273, 57563, 406465. This sequence is OEIS A232215 but its a bit hard to see that given the non-combinatorial description.