Count the number of a kind of matrix I want to count the number of $M\times N$ matrices with $0s$ and $1s$ which have exactly $k$ $1s$ and of which each column and each row has a least one 1. It is a little difficult for me. Could anyone help me ? Thanks in advance!
 A: The number $\lambda(M, N, k)$, $0 \leq k \leq MN$, of $M \times N$ matrices with precisely $k$ entries $1$ and all other entries $0$ in each column is $${{MN}\choose{k}}.$$
We must subtract from this the number of matrices that fail the row/column condition. Note that any such matrix has a zero row or column, and deleting this row or column yields a $M \times (N - 1)$ or $(M - 1) \times N$ matrix with precisely $k$ entries $1$, which sets up a double induction and a (possibly complicated) inclusion-exclusion argument
One could try to work out the induction from the bottom up, using that $\lambda(M, 0, k) = \delta_{Mk}$ and adding one row or column at a time. The complication here will be that there is more than one way to generate a given admissible matrix from a matrix with fewer rows and columns.
Note that this $\lambda(M, N, k)$ grows very fast with $M, N$. For example, if $M = N = k$, the admissible matrices are precisely the permutation matrices of size $M$, so $$\lambda(M, M, M) = M!,$$ and an easy argument gives that $$\lambda(M, M, M + 1) = \frac{1}{2}M(M - 1) M !.$$
