4
$\begingroup$

I am trying to count the number of $(0,1)$ $m \times n$ matrices that contain exactly $k$ ones distributed such that no row and no column contains only zeros (clearly, $k \ge m$ and $k \ge n$ yield interesting cases). I looked at similar questions (e.g., here), but they usually do not contain global constraints such as the total number of ones. Similarly, unlike here, this question does not have any constraints on column/row sums.

Thanks in advance for your help!

$\endgroup$
4
  • $\begingroup$ @ClaudeLeibovici: Any reasoning why you think the attribute even is irrelevant? $\endgroup$ Mar 3, 2017 at 7:52
  • $\begingroup$ @amWhy: Any reasoning why you think the attribute even is irrelevant? $\endgroup$ Mar 3, 2017 at 13:59
  • 1
    $\begingroup$ I still don't see why this question is a duplicate of the one mentioned, and moreover the solution seems quite different. $\endgroup$
    – Boris
    Mar 4, 2017 at 12:20
  • 1
    $\begingroup$ You're right. These two questions are different in content and in their solution. It seems, the close-voters did a rather mindless job without appropriate reasoning. Nevertheless the answer from @bof is vey nice and compensates this rather poor close-voting. $\endgroup$ Mar 4, 2017 at 14:34

1 Answer 1

4
$\begingroup$

For instance, if $k=m\ge n,$ you are asking for the number of surjections from $[m]$ to $[n],$ a classical counting problem. Like the problem of counting surjections, your more general question has an answer in the form of an inclusion-exclusion formula: $$\sum_{u=0}^m\sum_{v=0}^n(-1)^{u+v}\binom mu\binom nv\binom{(m-u)(n-v)}k\tag1$$ or equivalently (setting $r=m-u,s=n-v$) $$\sum_{r=0}^m\sum_{s=0}^n(-1)^{m+n+r+s}\binom mr\binom ns\binom{rs}k.\tag2$$

Example. Consider the case $m=2,n=3,k=3.$ The answer is clearly $2^3-2=6.$ With $m=2$ and $n=3$ in formula (2), the only nonzero terms occur when $rs\ge3,$ that is, when $(r,s)$ is $(1,3)$ or $(2,2)$ or $(2,3),$ and we get $$-\binom21\binom33\binom33-\binom22\binom32\binom43+\binom22\binom33\binom63=-2-12+20=6.$$

Explanation. Let $E$ be the set of all $m\times n$ matrices of zeros and ones with exactly $k$ ones. For $i\in[m]$ let $A_i$ be the set of all matrices in $E$ with no ones in the $i^{\text{th}}$ row. For $j\in[n]$ let $B_j$ be the set of all matrices in $E$ with no ones in the $j^{\text{th}}$ column. The expression (1) comes from the inclusion-exclusion formula for $$|E\setminus(\bigcup_{i\in[m]}A_i\cup\bigcup_{j\in[n]}B_j)|\tag3$$ by simplifying it using the fact that, for $I\in\binom{[m]}u$ and $J\in\binom{[n]}v,$ $$|\bigcap_{i\in I}A_i\cap\bigcap_{j\in J}B_j|=\binom{(m-u)(n-v)}k.\tag4$$

$\endgroup$
1
  • $\begingroup$ Thank you! Could you please point me to some argument about correctness? $\endgroup$
    – Boris
    Mar 2, 2017 at 13:06

You must log in to answer this question.

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