مساله را برای حالت کلی ماتریس های $m \times n$ حل می کنیم:
اول خیال خود را از صفر بودن ستونها راحت می کنیم پس فرض کنید که $X$ تمام ماتریسهای $m \times n$ با درایه های $0,1$ باشد که در هر ستون حداقل یک $1$ باشد یعنی هر ستون غیر صفر باشد.هر مکان هر ستون را با دو حالت $0,1$ می توان ساخت و هر ستون $m$ مکان دارد اما باید ستون صفر را کنار گذاشت و چون $n$ ستون داریم بنا به اصل ضرب:
$n(X)=(2^m-1)^n$
حال باید خیال خود را از صفر نبودن سطرها راحت کنیم.فرض کنید که برای هر $1 \leq k \leq m-1$ ، $A_k$ اعضایی از $X$ باشد که تعداد سطرهای صفر آن $k$ است.بنابه استدلال قبل:
$n(A_k)=(2^{m-k}-1)^n$.
پس اگر $f(m,n)$ تعداد ماتریس های مطلوب ما باشد بنا به اصل شمول و عدم شمول:
$f(m,n)=(A_1 \cup A_2 \cup ... \cup A_{m-1})^c=n(X)-(A_1 \cup A_2 \cup ... \cup A_{m-1})$
$=(2^m-1)^n- m(2^{m-1}-1)+ \binom{m}{2} (2^{m-2}-1)^n-...+(-1)^{m-1} \binom{m}{m-1}(2^1-1)^n$
$= \sum _{k=1}^m(-1)^k \binom{m}{k}(2^{m-k}-1)^n $
واضح است که اگر اول روی سطرها کار کنیم بعد روی ستونها، $f(m,n)=f(n,m)$.
$ \Box $
