Enumerating 0-1 finite boxes without null rays.

Question

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)=? $

Answer 1

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

Answer 2

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.