An interesting combinatorics problem

Hint: The following reformulation of the problem might be useful:

Consider $(0,1)$-matrices with $m$ rows and $n$ columns. Find the number of $(0,1)$-matrices so that for each two rows there is at least one position $j\ (1\leq j \leq n)$ where both rows have a $1$ at this position.

Here we consider wlog $A=[n]=\{1,2,\ldots,n\}$ and encode the subset $\emptyset\ne P_k\subset A$ with the $k$-th $(1\leq k\leq m)$ row. The position $j$ in the $k$-th row is $1$ iff $j\in P_k$.

Small values:

With the help of a little R code we obtain for small values of $m$ and $n$ the number $S(n,m)$ of admissible matrices as

$$ \begin{array}{c|rrrrrrr} m\backslash n&1&2&3&4&5&6&\cdots\\ \hline 1&1&3&7&15&31&63&\cdots\\ 2&1&7&37&175&781&3\,367&\cdots\\ 3&1&15&175&1\,827&17\,791&\cdots\\ 4&1&31&781&17\,887&\cdots\\ 5&1&63&3\,367&\cdots\\ \vdots&\\ \end{array} $$

We find in OEIS the values of $S(n,m)$ for

• $m=1$ as A000225 the number of non-empty subsets with $n$ elements.

\begin{align*} S(n,1)&=(1,3,7,15,31,\ldots)\\ &=(2^n-1)_{n\geq 1} \end{align*}

• $m=2$ as A005061 the number of binary $(2\times n)$-arrays with a path of adjacent $1$'s from top row to bottom row.

\begin{align*} S(n,2)&=(1,7,37,175,781,3\,367,\ldots)\\ &=(4^n-3^n)_{n\geq 1} \end{align*}

• $m=3$ as A051588 the number of binary $(3\times n)$-matrices such that any $2$ rows have a common $1$.

\begin{align*} S(n,3)&=(1,15,175,1\,827,17\,791,\ldots)\\ &=(8^n-3\cdot 6^n+3\cdot5^n-4^n)_{n\geq 1} \end{align*}

• $m=4$ as A051587 the number of binary $(4\times n)$-matrices such that any $2$ rows have a common $1$.

\begin{align*} S(n,4)&=(1,31,781,17\,887,\ldots)\\ &=(16^n -6\cdot 12^n +12\cdot 10^n -9^n\\ &\qquad-16\cdot 8^n +15\cdot 7^n -6\cdot 6^n +5^n)_{n\geq 1} \end{align*}

• $m=5$ as A051589 the number of binary $(5\times n)$-matrices such that any $2$ rows have a common $1$.

\begin{align*} S(n,5)&=(1, 63, 3\,367, \ldots)\\ &=(32^n - 10\cdot 24^n + 30\cdot 20^n - 5\cdot 18^n + 5\cdot 17^n\\ &\qquad - 70\cdot 16^n - 30\cdot 15^n + 135\cdot 14^n + 30\cdot 13^n\\ &\qquad- 140\cdot 12^n - 2\cdot 11^n + 130\cdot 10^n - 110\cdot 9^n\\ &\qquad+ 45\cdot 8^n - 10\cdot 7^n + 6^n)_{n\geq 1} \end{align*}

Note: We observe that $S(n,m)$ has for $1\leq m\leq 5$ a representation as alternating sum of certain powers of $n$. When we recall that ${n\brace k}$ the Stirling numbers of the second kind gives the number of partitions of $n$ elements into $k$ non-empty subsets and a representation can be given as alternating sum of powers of $n$ \begin{align*} {n\brace k}=\frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n \end{align*} this indicates that a summation formula for $S(m,n)$ including Stirling numbers of the second kind should be within reach.

1 ) Premise

Consider a $(m \times n)$ binary matrix $\boldsymbol{A}$ as already indicated by Markus.

Each row represents a subset of the set $\{1, \cdots,n\}$, and we shall have that each of the $m$ rows has at least one $'1'$ on the same column with any of the others.
In other words: that no row vector be normal to any of the others, or that $\boldsymbol {AA^T}$ does not contain zero values.

The all zeros vector = empty vector is normal to itself and to any other vector, and shall be accounted carefully.
We follow here the strategy to include it in the computations and elide it at the proper step.

We have $2^n$ possible vectors (empty included), and, since they can be repeated, $2^{nm}$ possible matrices.

2) Normal vectors

Consider a vector with $q$ ones. Clearly all the vectors normal to that shall have $q$ $'0'$s corresponding to the $'1'$s, and whatever value in the remaining positions. $$ \bbox[lightyellow] { \begin{array}{c|cccccc} {} & 1 & 2 & 3 & \cdots & {n - 1} & n \\ \hline {\mathbf{V}_{\,q} \;\;:q\;'1'} & 1 & 0 & 1 & \cdots & 0 & 1 \\ {\mathbf{V}_{\,q \bot } : \bot \mathbf{V}_{\,q} } & \text{0} & \text{x} & \text{0} & \cdots & \text{x} & \text{0} \\ \end{array} } \tag{1}$$

There are ${n \choose q}$ vectors with $q$ ones, $2^{n-q}$ vectors normal to each of them , $2^{n}-2^{n-q}$ vectors
not normal.

Since the second vector is repeated, we can sum the above over $q$ to get the number of couples of vectors normal to each other $$ \bbox[lightyellow] { H_{\,2} = \sum\limits_{0\, \le \,q\, \le \,n} {\left( \matrix{ n \cr q \cr} \right)2^{\,n - q} } = \sum\limits_{0\, \le \,q\, \le \,n} {\left( \matrix{ n \cr q \cr} \right)2^{\,q} } = \left( {1 + 2} \right)^{\,n} = 3^{\,n} } \tag{2}$$

To append a third vector normal to the 1st and 2nd we repeat the scheme above: - ${n \choose q_1}$ ways to choose the 1st vector - ${{n-q_1} \choose q_2}$ ways to choose the 2nd vector - $2^{n-q_{1}-q_{2}}$ ways to choose the 3rd vector $$ \bbox[lightyellow] { \eqalign{ & H_{\,3} = \sum\limits_{0\, \le \,q_{\,1} \, \le \,n} {\sum\limits_{0\, \le \,q_{\,2} \, \le \,n} {\left( \matrix{ n \cr q_{\,1} \cr} \right)\left( \matrix{ n - q_{\,1} \cr q_{\,2} \cr} \right)2^{\,n - q_{\,1} - q_{\,2} } } } = \cr & = 2^{\,n} \sum\limits_{0\, \le \,q_{\,1} \, \le \,n} {\left( \matrix{ n \cr q_{\,1} \cr} \right)\left( {\sum\limits_{0\, \le \,q_{\,2} \, \le \,n} {\left( \matrix{ n - q_{\,1} \cr q_{\,2} \cr} \right)2^{\, - q_{\,2} } } } \right)2^{ - q_{\,1} } } = \cr & = 2^{\,n} \left( {1 + 1/2} \right)^n \sum\limits_{0\, \le \,q_{\,1} \, \le \,n} {\left( \matrix{ n \cr q_{\,1} \cr} \right)3^{ - q_{\,1} } } = 3^n \left( {1 + {1 \over 3}} \right)^n = 4^n \cr} } $$

It is easy to check that we can write the above as $$ \bbox[lightyellow] { \eqalign{ & H_{\,3} (n) = \sum\limits_{0\, \le \,q_{\,1} \, \le \,n} {\sum\limits_{0\, \le \,q_{\,2} \, \le \,n} {\left( \matrix{ n \cr q_{\,1} \cr} \right)\left( \matrix{ n - q_{\,1} \cr q_{\,2} \cr} \right)2^{\,n - q_{\,1} - q_{\,2} } } } = \cr & = \sum\limits_{0\, \le \,q_{\,2} \, \le \,n} {\left( \matrix{ n \cr q_{\,2} \cr} \right)H_{\,2} (n - q_{\,2} )} \cr} }$$ and thus that we can generalize them to get the number of mutually normal $h$-uples $$ \bbox[lightyellow] { H_{\,h} = \left( {h + 1} \right)^{\,n} } \tag{3.a}$$ and that their number excluding the empty vector $H_ {* _{\,h}}$ is $$ \bbox[lightyellow] { H_{\,h} = \left( {h + 1} \right)^{\,n} = \sum\limits_{0\, \le \,j\, \le \,n} {\left( \matrix{ n \cr j \cr} \right)h^{\,n - j} } \quad \Rightarrow \quad H_{ * _{\,h}} = h^{\,n} } \tag{3.b}$$

Let's now note that for 2 vectors normal to a third are not necessarily mutually normal.
$$ \bbox[lightyellow] { \left( {1 \bot 2} \right) \cap \left( {1 \bot 3} \right) \cap \left( {2 \bot 3} \right) \ne \left( {1 \bot 2} \right) \cap \left( {1 \bot 3} \right) }$$ So we need to refer back to the table (1) and imagine to add further rows with $y,z, ..$ etc. in correspondence of the $x$'s, and then refer to (2) to get $$ \bbox[lightyellow] { H_{1,\,m} = \left| {\,\left( {1 \bot 2} \right) \cap \left( {1 \bot 3} \right) \cap \cdots \cap \left( {1 \bot m} \right)\,} \right| = \left( {1 + 2^{m - 1} } \right)^n } \tag{4.a}$$

But, when there is not a common vector $$ \bbox[lightyellow] { \left| {\,\left( {1 \bot 2} \right) \cap \left( {3 \bot 4} \right)\,} \right| = H_{\,2} ^2 } \tag{4.b}$$

3) $m$-uples with at least one normal couple

At this step we shall compute the number of $m$-uples of vectors that contains one or more couples.

To this scope we can resort to the inclusion-exclusion principle.

So for $m=3$ we get $$ \bbox[lightyellow] { \eqalign{ & Q_{\,3} = \left| {\,\left( {1,2} \right) \cup \left( {1,3} \right) \cup \left( {2,3} \right)\,} \right| = \cr & = \left| {\,\left( {1,2} \right)\,} \right| + \left| {\,\left( {1,3} \right)\,} \right| + \left| {\,\,\left( {2,3} \right)} \right| + \cr & - \left| {\,\left( {1,2} \right) \cap \left( {1,3} \right)\,} \right| - \left| {\,\left( {1,2} \right) \cap \left( {2,3} \right)\,} \right| - \left| {\,\left( {1,3} \right) \cap \left( {2,3} \right)\,} \right| + \cr & + \left| {\,\left( {1,2} \right) \cap \left( {1,3} \right) \cap \left( {2,3} \right)\,} \right| = \cr & = 3H_{\,2} 2^{\,n} - 3H_{\,1,3} + H_{\,3} = 3 \cdot 3^{\,n} \cdot 2^{\,n} - 3 \cdot 5^{\,n} + 4^{\,n} = \cr & = 3\left( {6^{\,n} - 5^{\,n} } \right) + 4^{\,n} \cr} } \tag{5}$$ which includes the null vector.

It returns $1,\, 7,\,49,\,337,\,2296,\,14977,\,97189,\,\cdots\quad|\;n=0,1,\cdots$ which checks with computation.
Interesting to note that, when complemented ($\overline Q _m = 2^{\,m\,n} - Q_m $) it gives $$0,\, 1,\,15,\,175,\,1827,\,17791,\,164955,\,\cdots$$ that is the sequence indicated by Markus, and which is a logical deduction from the inclusion-exclusion principle.

It remains to find a suitable extension of the formula above to general values of $m$, that allows to by-pass the inclusion-exclusion formula, also considering the difficulty introduced with (4.b).