For $m > n$, I want to calculate the number of binary matrices with $m$ rows and $n$ columns for which two conditions hold:


* the rank of a matrix is $n$ (i.e. it is full-rank, as $m > n$);
* there are no rows with a single 1 - in other words, there are no rows of Hamming weight 1.


I need either closed formula or some polynomial-time algorithm to calculate this number (for example via some recurrent formula).


**Note**. "Binary" means that matrix is considered over Galois field $\mathbb F\_2$.



Number of full-rank binary matrices with no rows of weight 1
First let us count the number of matrices $m\times n$ over $\mathbb F\_2$ of full rank (without the second restriction). Let $r\_i$ ($i=1,2,\dots,m$) be the $i$-th row of such a matrix, $V\_i=\langle r\_1,\dots,r\_i\rangle$ be the vector space spanned by the first $i$ rows, and $d\_i = \dim V\_i$. Then $|V\_i|=2^{d\_i}$, and $d\_0=0, d\_1=1, d\_2, \dots, d\_{m-1}, d\_m=n$ forms a nondecreasing sequence.


Now, let us pick the set of indices $I\subset [m]:=\{1,2,\dots,m\}$ such that $d\_i=d\_{i-1}+1$ for all $i\in I$. Clearly, we have $|I|=n$, $\{ d\_i\mid i\in I\}=[n]$, and $\{ d\_{i-1}\mid i\in I\}=\{0,1,\dots,n-1\}$. The rows with indices from $I$ form a nondegenerate $n\times n$ matrix, which we denote $M\_I$. Furthermore, for every $i\in[m]$, we have $r\_i\notin V\_{i-1}$ if $i\in I$, and $r\_i\in V\_{i-1}$ if $i\notin I$.


The number of matrices $M\_I$ can easily computed: its rows are formed by arbitrary elements of the complements $\mathbb F\_2^n \setminus V\_{i-1}$ of size $2^n - 2^{d\_{i-1}}$ (where $i\in I$), and so the number of such matrices is
$$f\_n = \prod\_{i\in I} (2^n - 2^{d\_{i-1}})=\prod\_{j=0}^{n-1} (2^n - 2^j).$$


We can view the original $m\times n$ matrix as $M\_I$ "augmented" with $m-n$ rows of indices $i\notin I$. If the number of preceding elements from $I$ to such an index is $t$ ($0\leq t\leq n$), then the row can take $2^t$ different values (e.g., for $t=0$ we can have only the zero vector, and thus the number of values is $2^0=1$). We remark that the choice of particular $t\_1\leq t\_2\leq \dots\leq t\_{m-n}$ from $\{0,1,\dots,n\}$ fully determines the set $I$ itself.


The above analysis implies that the number of matrices we look for is the coefficient of $x^{m-n}$ in $f\_n\cdot \prod\_{t=0}^n \frac{1}{1-2^tx}$, which is the same as the coefficient of $x^{m+1}$ in
$$F\_n(x) = f\_n\cdot \prod\_{t=0}^n \frac{x}{1-2^tx}.$$




---


We will also need a modification of the above formula that addresses the case of matrices with exactly $z$ zero rows. It is not hard to see that the number of such matrices is given by the coefficient of $x^{m}$ in
$$G\_{m,n,z}(x) = \binom{m}{z}\cdot x^z\cdot f\_n\cdot\prod\_{t=1}^n \frac{x}{1-(2^t-1)x}.$$
This can be proved by first removing the zero rows from a matrix, and then by proceeding as above. The only difference is that the augmentation now cannot use zero vectors, each time leaving us with just $2^t-1$ values for a row instead of $2^t$.




---


Now, let us address the restriction on rows with single 1. We will use the inclusion-exclusion to do so.


Let $P\_i$ ($i=1,\dots,n$) be the property that there is a row with single 1 at $i$-th coordinate. Suppose that an $m\times n$ matrix satisfy properties with indices from a set $R$ with $|R|=k$. 
Then the set of row indices is partitioned as
$$[m] = J \sqcup \overline{J},$$
where $J$ consists of the indices corresponding to rows with single 1 at a coordinate from $R$. Let $j=|J|$ (we have $j\geq k$).


To enumerate the possible submatrices at $J\times [n]$, we notice that their columns essentially define an ordered partition of their rows into $k$ nonempty subsets. Hence, the number of such submatrices equals $k!\cdot S(j,k)$, where $S(\cdot,\cdot)$ is Stirling number of second kind. 


The number of submatrices at $\overline{J}\times \overline{R}$ with exactly $z$ zero rows is given by the coefficient of $x^{m-j}$ in $G\_{m-j,n-k,z}(x)$. They can be extended to submatrices at $\overline{J}\times [n]$ in $(2^k-k)^z\cdot (2^k)^{m-j-z}$ ways.


Putting all together and using inclusion-exclusion, we conclude that the required number of matrices (not satisfying any properties $P\_i$) equals the coefficient of $x^m$ in
$$\begin{split}
&\sum\_{k=0}^n (-1)^k \binom{n}{k} \sum\_{j=k}^m \binom{m}{j}\cdot k!\cdot S(j,k) \sum\_{z=0}^{m-j} x^j\cdot G\_{m-j,n-k,z}(x)\cdot (2^k-k)^z\cdot (2^k)^{m-j-z}\\
=&
n!\sum\_{k=0}^n (-1)^k \frac{f\_{n-k}}{(n-k)!}\cdot\prod\_{t=1}^{n-k} \frac{x}{1-(2^t-1)x}\cdot\sum\_{j=k}^m \binom{m}{j}\cdot S(j,k)\cdot \left(2^k+(2^k-k)x\right)^{m-j}\cdot x^j\\
=&\sum\_{k=0}^n \binom{n}{k}\cdot f\_{n-k}\cdot\prod\_{t=1}^{n-k} \frac{x}{1-(2^t-1)x}\cdot \sum\_{\ell=0}^k (-1)^\ell\cdot \binom{k}{\ell}\cdot \left(2^k+(2^k-k+\ell)x\right)^m.
\end{split}$$




---


**UPDATE.** We can also get an explicit answer without using generating functions. As Yauhen noticed, 
$$[x^{m+1}]\ F\_n(x) = \prod\_{t=0}^{n-1} (2^m - 2^t).$$
Then the number of full-rank matrices with exactly $z$ zero rows can be obtained with inclusion-exclusion as
$$[x^m]\ G\_{m,n,z}(x) = \binom{m}{z}\sum\_{p=0}^{m-z} (-1)^{m-z-p} \binom{m-z}{p} \prod\_{t=0}^{n-1} (2^p - 2^t).$$
Using this expression, we can restate the number of full-rank matrices not satisfying any properties $P\_i$ as
$$\begin{split}
&\sum\_{k=0}^n (-1)^k \binom{n}{k} \sum\_{j=k}^m \binom{m}{j}\cdot k!\cdot S(j,k) \sum\_{z=0}^{m-j} \binom{m-j}{z}\cdot (2^k-k)^z\cdot (2^k)^{m-j-z}\\
\times&\sum\_{p=0}^{m-j-z} (-1)^{m-j-z-p} \binom{m-j-z}{p} \prod\_{t=0}^{n-k-1} (2^p - 2^t)\\
=&\sum\_{k=0}^n (-1)^k \binom{n}{k} \sum\_{j=k}^m \binom{m}{j}\cdot k!\cdot S(j,k) \sum\_{p=0}^{m-j} (-1)^{m-j-p} \binom{m-j}{p}\cdot 2^{kp}\cdot k^{m-j-p} \prod\_{t=0}^{n-k-1} (2^p - 2^t)\\
=&\sum\_{k=0}^n \binom{n}{k} \sum\_{\ell=0}^k (-1)^{k-\ell}\cdot \binom{k}{\ell} \sum\_{p=0}^{m} \binom{m}{p}\cdot 2^{kp}\cdot (-\ell)^{m-p} \prod\_{t=0}^{n-k-1} (2^p - 2^t)\\
=&\sum\_{k=0}^n \binom{n}{k}\cdot k! \sum\_{p=0}^{m} (-1)^{m-p}\cdot \binom{m}{p}\cdot 2^{kp}\cdot S(m-p,k) \prod\_{t=0}^{n-k-1} (2^p - 2^t).
\end{split}
$$


