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?
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$– Per AlexanderssonCommented Nov 20, 2020 at 14:28
-
$\begingroup$ See mathoverflow.net/questions/151268/… for (only) slightly more general problem. $\endgroup$– Boris BukhCommented Nov 20, 2020 at 14:31
-
1$\begingroup$ See oeis.org/A008300 and the references given there. $\endgroup$– Ira GesselCommented 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$– Sidharth GhoshalCommented 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$– Sam HopkinsCommented Nov 20, 2020 at 20:29
|
Show 3 more comments
3 Answers
$\begingroup$
$\endgroup$
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.
answered Nov 20, 2020 at 19:48
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
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.
