# Number of matrices with no repeated columns or rows

If you consider all $m$ by $n$ matrices with entries that are either $0$ or $1$, there are ${2^{n} \choose m}$ with no repeated rows (up to row permutation) and ${2^{m} \choose n}$ with no repeated columns (up to column permutation). Is it possible to get an explicit estimate for how many there are with neither any repeated rows nor columns (up to either row or column permutation)? I am interested in the case where $m$ is large and $m \leq n \leq m^2$.

[Extended version of a previous unanswered MSE question ]

• Almost all matrices of these dimensions have no repeated rows or columns (the probability that two rows are the same is bounded by $\binom m2 2^{-n}$ and the probability that two columns are the same is at most $\binom n2 2^{-m}$. So a good estimate is $2^{nm}$. – Anthony Quas Feb 22 '14 at 22:03
• Continuing Anthony's comment, almost none of them have any symmetries either (slightly harder to prove) so to allow for row and column permutations asymptotically just divide my $m!\,n!$. – Brendan McKay Feb 23 '14 at 1:30
• The problem of counting these matrices up to row and column permutations is solved in I. M. Gessel and J. Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612, available online at arxiv.org/abs/0705.0042. (In the paper they are called "semi-point-determining bicolored graphs".) Of course, as in most unlabeled graphical enumeration problems, the formula is not simple, and might not be so helpful in deriving an asymptotic formula. The numbers in Richard's formula are sequence A181230 in the OEIS. – Ira Gessel Feb 23 '14 at 17:16

Let $f(m,n)$ denote the number of matrices being counted (not up to row and column permutation). We can try to compute $f(m,n)$ by Inclusion-Exclusion, allowing the rows to be distinct and sieving out the possible ways in which columns can be equal. This is just Möbius inversion on the lattice $\Pi_n$ of partitions of an $n$-element set. Plugging into the techniques of Enumerative Combinatorics, vol. 2, Section 5.1, gives $$F(x,y):=\sum_{m,n\geq 0} f(m,n)\frac{x^m}{m!}\frac{y^n}{n!} = \sum_{n\geq 0}(1+x)^{2^n}\frac{(\log(1+y))^n}{n!}.$$ It is curious that $F(x,y)=F(y,x)$. It shouldn't be difficult to get some good estimates for $f(m,n)$ from $F(x,y)$.