Number of full-rank binary matrices with no rows of weight 1 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$.
 A: 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}
$$
