3
$\begingroup$

Here rays are called lines. Call $M(a_1,a_2)$ the number for matrices of length $a_1$ and height $a_2$, made of $0$ and $1$, having neither null vector nor null co-vector. In other words any line (row or column) contains at least one $1$.
QUESTION 1 : How to count them?
QUESTION 2 : Same as above in higher dimensions.

It looks like a standard problem:

For example $M(1,p) =1$ , $M(2,p) = 3^p -2$ , $M(3,p) = 7^p -3.3^p +3$ , $M(4,p) = 15^p -4.7^p + 6.3^p -4$ The closed formula being clear but I have no clean proof for it.

Question for higher dimensions; for a cube $M(a_1,a_2,a_3)$ in $0-1$ ($2^{a_1a_2a_3}$ of them) with no null lines (in any of the three directions ).
For example $M(2,2,2) = 35$ (by hand).

Is there a closed formula for M(a_1,a_2,...a_k) in particular k = 3,4?

It seems that things change a lot when passing from k=2 to k=3, Even for k=3 and constraining last dimension to 2 : $M(a_1,a_2,2)=? $

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think something is wrong with your examples since clearly $M(a_1,a_2)=M(a_2,a_1)$ but your formulas give $M(3,4)=2161$ and $M(4,3)=1421$. Anyways, here is $M(a,a)$: oeis.org/A048291 $\endgroup$
    – Casteels
    Mar 29, 2013 at 19:26
  • $\begingroup$ $M(4,p)=15^p−4\cdot 7^p+6\cdot 3^p−4$. The general 2-D case a simple inclusion-exclusion. Higher dimensions are harder. $\endgroup$
    – Brendan McKay
    Mar 30, 2013 at 6:04
  • $\begingroup$ @Casteels : OK you are right there was a typo the 4 and the 6 where exchanged in front of the powers ^p. $\endgroup$
    – Jérôme JEAN-CHARLES
    Mar 30, 2013 at 18:21
  • $\begingroup$ See also Stanley, Enumerative Combinatorics Vol. 1 (2nd edition), Exercise 2.25(a). $\endgroup$
    – Sam Hopkins
    Jun 26, 2021 at 15:28

2 Answers 2

Reset to default
2
$\begingroup$

Define $$ N(m,r,s) = \begin{cases} 0 & \text{if } r+s\gt m, \text{ otherwise} \\\\ 3^m-2 & \text{if } r=s=0 \\\\ 3^{m-s}-1 & \text{if } r=0,s\gt 0, \\\\ 3^{m-r}-1 & \text{if } r\gt 0,s=0, \\\\ 3^{m-r-s} & \text{if } r,s\gt 0. \end{cases} $$ Then $$ M(m,n,2) = \sum_{r,s,\ge 0} (-1)^{r+s} \binom{m}{r,s,m-r-s} N(m,r,s)^n. $$

For $M(n,n,2)$ I get 1, 35, 12757, 35420099, 780742441861, 145246791109197875, ...

Not in OEIS (and shouldn't be put there without checking).

Proof: $N(m,r,s)$ is the number of $2\times m$ binary arrays such that none of the $m+2$ lines sum to 0, and moreover a specified set of $r$ positions in the top row are 0 and a disjoint specified set of $s$ positions in the bottom row are 0. Now make an array by placing $n$ such arrays vertically. There are $2m$ horizontal lines which we still have to make non-zero. The multinomial counts the ways to choose $r$ positions in the top row and $s$ in the bottom row (which must be disjoint positions or one of the 2-element lines is zero). The formula is then just inclusion-exclusion.

The asymptotic number is $$ N(n,n,2) \sim 3^{n^2}, $$ which is easy to prove.

Another case: $M(n,2,2)$ is 1, 35, 313, 2339, 16681, 117395, 823033, 5763779, 40351561, 282471155, 1977318553, 13841270819, ... The sum above only has 4 non-zero terms so there is an explicit formula. Maybe it is $M(n,2,2) = 7^n - 2^{n+2} + 2$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ To get your formula for $M(n,2,2)$ via inclusion-exclusion, stack $n$ levels of $2 \times 2$ matrices, then use $M(2,2)=7$ to overcount the number of ways to fill each level. This includes $4 \cdot 2^n$ cases where one of the four $n$-lines is all $0$s, and that overcounts the $2$ cases when two lines are all $0$s. The same inclusion/exclusion idea gives $M(n,3,2) = 25^n -6(8^n+3^n) +6(3\cdot2^n +1)$, and the asymptotics $M(m,n,p) \sim M(m,n)^p$. $\endgroup$
    – Zack Wolske
    Mar 30, 2013 at 10:51
1
$\begingroup$

To extrapolate on Brendan McKay's comment for question one, here is a recurrence for $M(m,n)$. Though not exactly an inclusion exclusion argument (it's not hard to turn it into one), this essentially counts the matrices with no null rows two ways.

For matrices of size $m \times n$, there are $(2^n-1)^m$ with at least one $1$ in each of the $m$ rows, since each row can be anything but the all $0$ vector.

On the other hand, given $k$ columns, there are $M(m,k)$ matrices with at least one $1$ in each row, and in each of those $k$ columns, and all $0$s in the other columns. If a matrix in the first count fails to have at least one $1$ in each column, then it has some number of all $0$ columns - at least $1$, and at most $n-1$. This gives $$ M(m,n) = (2^n-1)^m - \sum_{k=1}^{n-1}\binom{n}{k}M(m,k) $$ Putting the summation on the other side gives the counts of matrices with no null rows.

Attempting to generalize this to higher dimensions didn't get past the very small numbers before breaking into a plethora of cases - even $M(m,3,2)$ and $M(m,3,3)$ are difficult. Maybe you can see a better way to extend it than I can.

Improve this answer
$\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.