Proving that $\sum_{i\geq0}f_i(n,m)x^i=\sum_{k=0}^n(-1)^k{n \choose k}\big((1+x)^{n-k}-1\big)^m$ Let $f_i(n,m)$ ($n,m\geq1i\geq0$) be the number of $m\times n$ matrices with entry of 0 and 1, so that there is in each row and column at least one 1 and total exactly i ones.
I have to show that:
$\sum_{i\geq0}f_i(n,m)x^i=\sum_{k=0}^n(-1)^k{n \choose k}\big((1+x)^{n-k}-1\big)^m$
Can you help me to do that? 
 A: 
Hi
Let $f_{i,j}$ be the matrices that have $i$ $0's$ and the row $j$ is $(0,0,\ldots ,0)$ and let $\hat{f}_{i,j}$ be the matrices that have $i$ $0's$ and the colum $j$ is $(0,0,\ldots ,0)^T$.
Then
$$f_i(n,m)=|\binom{[n*m]}{i}\setminus (\bigcup _{k=1}^n f_{i,k} \cup \bigcup _{j=1}^m \hat{f}_{i,j})|.$$
By inclusion-exclusion you have the following $$f_i(n,m)=\binom{n*m}{i}-\sum _{k=1}^n\sum _{j=1}^m (-1)^{k+j-1}\sum _{a_1<a_2<\cdots<a_k,b_1<b_2<\cdots <b_j}|(\bigcap _{p=1}^k f_{i,a_p} \cap \bigcap _{q=1}^j \hat{f}_{i,b_q})|$$
But then you have $(n-k)(m-j)$ choices to put the $i$ ones, so.
$$f_i(n,m)=\binom{n*m}{i}-\sum _{k=1}^n\sum _{j=1}^m (-1)^{k+j-1}\sum _{a_1<a_2<\cdots<a_k,b_1<b_2<\cdots <b_j}\binom{(n-k)(m-j)}{i}$$
But that does not depend on the choice of the rows or the columns, so
$$f_i(n,m)=\binom{n*m}{i}-\sum _{k=1}^n\sum _{j=1}^m (-1)^{k+j-1}\binom{n}{k}\binom{m}{j}\binom{(n-k)(m-j)}{i}$$
Note that the indices are just notation in the sense that i could have 1 row and 0 columns or 1 column and 0 rows, the only thing i could not have was 0 rows and 0 columns, but that's actually counted by $\binom{n*m}{i}$, so
$$f_i(n,m)=\sum _{k=0}^n\sum _{j=0}^m (-1)^{k+j}\binom{n}{k}\binom{m}{j}\binom{(n-k)(m-j)}{i}$$
Can you take it from here?
Notice that the last binomial might come from the binomial theorem applied to the last term you have.
Edit:
So you want to calculate $\sum _{r\geq 0}f_r(n,m)x^r$, first notice that if $r>n*m$, then $f_r(n,m)=0$. So
$$\sum _{r=0}^{nm}f_r(n,m)x^r=\sum _{r=0}^{nm}(\sum _{k=0}^n\sum _{j=0}^m (-1)^{k+j}\binom{n}{k}\binom{m}{j}\binom{(n-k)(m-j)}{r})x^r$$
By commutativity, you get
$$\sum _{r=0}^{nm}f_r(n,m)x^r=\sum _{k=0}^n(-1)^{k}\binom{n}{k}\sum _{j=0}^m (-1)^{j}\binom{m}{j}\sum _{r=0}^{nm}(\binom{(n-k)(m-j)}{r}x^r)$$
By the binomial theorem applied to the last sum, you get
$$\sum _{r=0}^{nm}f_r(n,m)x^r=\sum _{k=0}^n(-1)^{k}\binom{n}{k}\sum _{j=0}^m (-1)^{j}\binom{m}{j}(x+1)^{(n-k)(m-j)}$$
Again binomial theorem
$$\sum _{r=0}^{nm}f_r(n,m)x^r=\sum _{k=0}^n(-1)^{k}\binom{n}{k}((x+1)^{(n-k)}-1)^m$$
And that's all.
