8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I assume that you want the entries to be nonnegative integers?! $\endgroup$ – Igor Rivin Oct 11 '16 at 20:05
  • $\begingroup$ This would make a good undergraduate exercise in combinatorics. Can you tell us the source and motivation of the problem? Gerhard "Hint: Think Jordan Normal Form" Paseman, 2016.10.11. $\endgroup$ – Gerhard Paseman Oct 11 '16 at 20:20
  • 1
    $\begingroup$ Yes, the entries are nonnegative integers. I am trying to find an upper bound of the number of different Dessin D'enfants for trigonal curves with a given maximal degree $n$. Thanks. $\endgroup$ – Mehmet Aktas Oct 11 '16 at 20:32
  • $\begingroup$ Note that you can diagonalize the 3's and 2's, and reduce it to the problem of counting mxm matrices whose entries are all 1's (and zeros) and obey the same properties except the first L row and column sums are 2 and not 3. There should be an OEIS entry that will assist with this latter part. Gerhard "OK, Not Quite Jordan Form" Paseman, 2016.10.11. $\endgroup$ – Gerhard Paseman Oct 11 '16 at 20:42
  • $\begingroup$ I'm assuming invariance under both row and column permutations. If you have to separate things out according to just row or just column permutations, that can be done but the advice above has to be tweaked. Gerhard "Specializing In Combinatorial Matrix Theory" Paseman, 2016.10.11. $\endgroup$ – Gerhard Paseman Oct 11 '16 at 20:48
10
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I just saw Brendan McKay's post. I defer to his experience in these matters. Gerhard "Needs To Look Around More" Paseman, 2016.10.11. $\endgroup$ – Gerhard Paseman Oct 12 '16 at 0:51
  • $\begingroup$ I see from the expanded question that I left out a case. Instead of s many 2x2 blocks, replace it by an sxs block with 2's on the diagonal and an off diagonal permutation represented by 1's. It may be that the remaining block has no 2's. In any case the upper bound still depends on the binary case, and does not change much asymptotically. Gerhard "Number Of Digits About Same" Paseman, 2016.10.12. $\endgroup$ – Gerhard Paseman Oct 12 '16 at 19:59

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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