2
$\begingroup$

Given a $N \times N$ binary matrix (aka {0,1}- matrix) and an integer $k, k<N$, how many matrices can be constructed such that each row and column in the constructed matrix sum up to exactly k?

$\endgroup$
8
  • 2
    $\begingroup$ In the world of symmetric functions, this correspond to finding the coefficient of m_kkk...k in e_kkk...kk, see math.upenn.edu/~peal/polynomials/… $\endgroup$ Nov 20, 2020 at 14:28
  • $\begingroup$ See mathoverflow.net/questions/151268/… for (only) slightly more general problem. $\endgroup$
    – Boris Bukh
    Nov 20, 2020 at 14:31
  • 1
    $\begingroup$ See oeis.org/A008300 and the references given there. $\endgroup$
    – Ira Gessel
    Nov 20, 2020 at 15:49
  • 1
    $\begingroup$ This is a cool problem! There ought to exist a generalization of the concept of an integer partition, that includes this as a special case. I wonder if such a theory is built if techniques from partitions can then the transferred into here. $\endgroup$ Nov 20, 2020 at 16:17
  • 2
    $\begingroup$ Note that if you allow $\mathbb{N}$ entries rather than $\{0,1\}$ entries, these are often called "magic squares" (see e.g. Section 4.6 of Stanley's EC1). Also, the more general thing where we specify arbitrary marginals (row and column sums) are called "contingency tables" and "(0,1) contingency tables." None of them are going to have easy exact formulas, but there are various kinds of estimates for these problems. $\endgroup$ Nov 20, 2020 at 20:29

3 Answers 3

4
$\begingroup$

There is no simple formula except for very small $k$ or $N-k$. The most general asymptotic formula, though it seems to have not appeared in print yet, is by Liebenau and Wormald and the references therein.

$\endgroup$
3
$\begingroup$

It seems like I've solved this or seen it before. The k=1 case is equivalent to the number of maximum independent sets on the nxn Rooks graph. The answer for k=1 is N!.

You're basically asking for how many ways to place nk rooks on a nxn board so that each row and column has exactly k rooks in it. I think this problem has been solved before. I'm on a cell phone so I don't have a link to the solution. However, I'm very confident it has been solved before.

Update: I take this back. I don't think it has a known solution, although I've played around with the question myself. This question states a solution isn't known for $N$ even and $k=\frac{N}{2}$:

Counting 2m X 2m 0-1 matrices with m ones in each row and each column.

The question is equivalent to your problem for a specific case of $k$.

$\endgroup$
1
$\begingroup$

Miller and Harrison (2013, link) solved this problem, even for arbitrary row and column margins per row and column ( link full text).

I think there was even a package, but sadly can't find it right now. Hope this helps.

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