The number of $m \times n$ binary matrices with all rows distinct and all columns distinct The entry A181230 of the OEIS says that the answer is $\sum_{i = 0}^m\sum_{j = 0}^n s(m, i) s(n, j) 2^{i * j}$ where I assume $s(a, b)$ denotes the Stirling number of the first kind. Can somebody help me understand this? I believe it involves the inclusion-exclusion principle. I looked at the wikipedia page for the inclusion-exclusion principle and using it involves choosing a collection of sets $A_i$ such that the union $\cup A_i$ is the thing we want to count but I can't see what choice of $A_i$ derives this formula.
 A: This one is a doozy. I have a partial answer, and a reference to hopefully help you complete it. This solution assumes you are comfortable with inclusion-exclusion and graph theory.

For each $1\le i<j\le m$, let $E_{ij}$ be the number of binary matrices where rows $i$ and $j$ are identical.
For each $1\le i<j\le n$, let $F_{ij}$ be the number of binary matrices where columns $i$ and $j$ are identical. 
We want the the number of matrices in none of these sets. To do this, we use inclusion exclusion; take all the matrices, $2^{mn}$, subtract the matrices where some $E_{ij}$ or $F_{ij}$ occurs, add back in the double intersections, etc. 


*

*There are $\binom{m}2$ sets of the form $E_{ij}$ and $\binom{n}2$ $F_{i,j}$. We are summing over all subsets of these; a bit of thought shows that we are summing over pairs of graphs $(G,H)$, where $G$ is a graph whose vertices are the rows, and $H$ is a graph whose vertices are the columns. 

*When considering the intersection of several $E_{ij}$ and $F_{ij}$, the connected components of the corresponding graphs must all be identical; if there is a path $(i_0,i_1),(i_1,i_2),\dots,(i_{k-1},i_k)$ so that the $i_{h}$ row is identical to the $i_{h+1}$ row, then by transitivity, the $i_0$ row and $i_k$ row are identical. 

*If the row graph has $i$ connected components, and the column graph has $j$ connected components, then the matrix decomposes into an $i\times j$ product of sets where the entries in each product must be identical, so there are $2^{ij}$ matrices in that intersection. 

*Finally, in inclusion exclusion, there is an alternating sign in the summation, given by the number of sets in the current intersection; this is the sum of the number of edges in each graph. 
Putting this all together, we have
$$
\sum_G\sum_H(-1)^{e(G)}(-1)^{e(H)}2^{k(G)k(H)}
$$
where 


*

*$G$ ranges all $2^{\binom{m}2}$ graphs on the rows, and $H$ ranges all $2^{\binom{n}2}$ graphs on the columns,

*$e(G)$ is the number of edges in $G$,

*$k(G)$ is the number of connected components in $G$.
This is looking a little bit like the form you want, but not quite. To simplify, let us collect all terms with a common value of $k(G)$ and $k(H)$. The  result is
$$
\sum_{i=1}^m\sum_{j=1}^n \Big(\sum_{\substack{G \text{ has $i$ connected}\\ \text{components}}}(-1)^{e(G)}\Big) \Big(\sum_{\substack{H \text{ has $j$ connected}\\ \text{components}}}(-1)^{e(H)}\Big)2^{ij}
$$
Therefore, letting $C(m,k)$ be the set of graphs on $m$ vertices with $k$ connected components, we will be done if we can show
$$
\sum_{G\in C(m,i)}(-1)^{e(G)} =s(m,i)
$$
I am not quite sure how to prove this; however, this other question handles the special case where $i=1$. I think the method there can be adapted to general $i$. Edit: Actually, this answer covers the general case exactly. 
