10
$\begingroup$

If $L(n, m)$ denotes the number of $n\times m$ matrices consisting only of $0$'s and $1$'s, such that there is no column or row consisting only of $0$'s, we get a nice recursive formula which enables us to compute them with ease: $$\sum_{j=1}^m \binom{m}{j} L(n, j) = (2^m-1)^n.$$

Now, let's consider two kinds of numbers, $L_1(n, m, p)$ and $L_2(n, m, p)$. The first kind of numbers will be the amount of $n\times m\times p$ cubes consisting only of $0$'s and $1$'s such that if we cross the cube with a line perpendicular to one of the axis, we get a non-zero vector. $L_2(n, m, p)$ is defined the same, expect that instead of taking lines, we take planes orthogonal to one of the axis. Clearly $L_1(n, m, p)\leq L_2(n, m, p)$.

Can we get a similar nice looking recursive formula for these numbers? Perhaps in terms of $L(n, m)$?

To be more precise, let me try to explain what exactly do I mean with $L_1(n, m, p)$. For example, you take some $1\leq i\leq n$, $1\leq j\leq m$ then for the cube $B$ we need to have $B_{ijk} = 1$ for some $1\leq k\leq p$.

Similarly, with $L_2(m, n, p)$ we can take some $1\leq i\leq n$, then there must be $1\leq j\leq m$, $1\leq k\leq p$ such that $B_{ijk} = 1$.

$\endgroup$
2
  • 1
    $\begingroup$ Just an idea how to compute $L(n,m)$ without recursive formula. For any $\{0,1\}$-matrix $A=(a_{ij})_{i,j=1}^{n,m}$ denote $f(A)=\prod_{k=1}^{m}(1-\prod_{i=1}^{n}(1-a_{ik}))\cdot\prod_{j=1}^{n}(1-\prod_{l=1}^{n}(1-a_{jl}))$. Then, for matrix $A$ which is satisfying given conditions we have $f(A)=1$, otherwise $F(A)=0$. Hence, number of such matrices is equal to $L(n,m)=\sum_{A\in\{0,1\}^{n,m}}f(A)$. I believe that we can expand $f$ and find closed form for this sum (but I haven't done that). The same thing can be done for 3-dimensional case. $\endgroup$
    – richrow
    Jul 5, 2020 at 18:57
  • 1
    $\begingroup$ @richrow: Hmm, yes, I like the idea, but I was unable to make it work. It seems to make the most sense to consider the $a_{il}$ to be i.i.d. Bernoulli random variables with $p=1/2$, and then we're just taking the expectation of your $f(A)$. However, the factors are not at all independent. One surely must use the fact that the expected value of a product of the $a_{il}$'s is $2^{-d}$ where $d$ is the number of distinct variables in the product. Unfortunately, applying that seems to become too much of a combinatorial mess. $\endgroup$ Jul 14, 2020 at 10:24

1 Answer 1

2
+100
$\begingroup$

One approach is classic inclusion-exclusion.

The argument is much simpler for $L_2(n,m,p)$. I'll use $1 \leq i \leq n$, $1 \leq j \leq m$, $1 \leq k \leq p$ throughout.

  • Let $P_i$ be the set of such matrices with $B_{i,j,k} = 0$ for all $j,k$.
  • Let $Q_j$ be the set of such matrices with $B_{i,j,k} = 0$ for all $i,k$.
  • Let $R_k$ be the set of such matrices with $B_{i,j,k} = 0$ for all $i,j$.

$P_i$ forces $mp$ entries to be $0$, so $|P_i| = 2^{nmp - mp}$. Similarly an $a$-fold intersection of $P_i$'s does not force $(n-a)mp$ entries to be $0$, so the result has size $2^{(n-a)mp}$. Likewise, an $a$-fold intersection of $P_i$'s intersected with a $b$-fold intersection of $Q_j$'s and a $c$-fold intersection of $R_k$'s does not force $(n-a)(m-b)(p-c)$ entries to be $0$, so has size $2^{(n-a)(m-b)(p-c)}$.

By the principle of inclusion-exclusion, the number of such matrices in none of these sets is

$$L_2(n,m,p) = \sum_{a=0}^n \sum_{b=0}^m \sum_{c=0}^p (-1)^{a+b+c} \binom{n}{a} \binom{m}{b} \binom{p}{c} 2^{(n-a)(m-b)(p-c)}. \qquad(*)$$

Analogous reasoning gives $$L(n,m) = \sum_{a=0}^n \sum_{b=0}^m (-1)^{a+b} \binom{n}{a} \binom{m}{b} 2^{(n-a)(m-b)}. \qquad(**)$$

You can go from (**) to your formula by repeated applications of the binomial theorem: $$\begin{align*} \sum_{m=0}^M \binom{M}{m} L(N,m) &= \sum_{m=0}^M \binom{M}{m} \sum_{a=0}^N \sum_{b=0}^m (-1)^{a+b} \binom{N}{a} \binom{m}{b} 2^{(N-a)(m-b)} \\ &= \sum_{a=0}^N (-1)^a \binom{N}{a} \sum_{m=0}^M \binom{M}{m} (2^{N-a}-1)^m \\ &= \sum_{a=0}^N (-1)^a \binom{N}{a} (2^{N-a})^M \\ &= (2^M-1)^N. \end{align*}$$

Similarly from (*) we get $$\sum_{m=0}^M \sum_{p=0}^P \binom{M}{m} \binom{P}{p} L_2(N,m,p) = (2^{MP}-1)^N$$ since the left-hand side is $$\begin{align*} &\sum_{a=0}^N (-1)^a \binom{N}{a} \sum_{m=0}^M \binom{M}{m} \sum_{b=0}^m (-1)^b \binom{m}{b} \sum_{p=0}^P \binom{P}{c} \sum_{c=0}^p (-1)^c \binom{p}{c} 2^{(N-a)(m-b)(p-c)} \\ &= \sum_{a=0}^N (-1)^a \binom{N}{a} \sum_{m=0}^M \binom{M}{m} \sum_{b=0}^m (-1)^b \binom{m}{b} \sum_{p=0}^P \binom{P}{c} (2^{(N-a)(m-b)}-1)^p \\ &= \sum_{a=0}^N (-1)^a \binom{N}{a} \sum_{m=0}^M \binom{M}{m} \sum_{b=0}^m (-1)^b \binom{m}{b} (2^{P(N-m)})^{m-b} \\ &= \sum_{a=0}^N (-1)^a \binom{N}{a} \sum_{m=0}^M \binom{M}{m} (2^{P(N-a)}-1)^m \\ &= \sum_{a=0}^N (-1)^a \binom{N}{a} (2^{MP})^{N-a} \\ &= (2^{MP}-1)^N. \end{align*}$$

(Obviously this will all generalize to hypercubes.)

You can get a formula for $L_1(m, p, n)$ along these lines, but the multi-fold intersections of the analogues of the $P$'s, $Q$'s, and $R$'s are significantly more annoying, since lines can either be skew or intersect. You'd need to index the intersections by subsets of $(i, j)$'s, $(j, k)$'s, and $(k, i)$'s, tracking how many times these collections themselves intersect. One would expect a recursive formula to exist, but it may not be transparent how to get one from this approach. Perhaps I'm overly pessimistic, but I see no reason to expect there to be a "nice" answer for $L_1(n, m, p)$.

$\endgroup$

You must log in to answer this question.

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