MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
How many symmetric and non-symmetric $n\times n$ matrices with $0/1$ entries are there such that every row is distinct and every column is distinct? (I am looking for a proof as well).
If only every row (or column) is distinct is needed, the answer is easy.
As suggested in comments, https://oeis.org/A088310 provides the numbers without symmetric restriction. I do not see a proof or link for proof there.
What about symmetric case?
For generic (not necessarily symmetric) $m\times n$ matrices over a set of $k$ elements, the number of those with pairwise distinct columns and rows is $$\sum_{i=0}^m\sum_{j=0}^n s(m,i)\cdot s(n,j)\cdot k^{i\cdot j},$$ where $s(,)$ are Stirling numbers of first kind with sign.
UPDATE. For symmetric $n\times n$ matrices over a set of $k$ elements, the number of those with pairwise distinct columns and rows is $$\sum_{i=0}^n s(n,i)\cdot k^{i(i+1)/2}.$$
For k=2, numerical values for $n=1,2,\dots$ are $$2, 6, 44, 716, 24416, 1680224, 229468288, \dots$$ and now form the sequence A259763 in the OEIS. Just in case, I have verified these values for $n\leq 5$ by a direct enumeration of matrices.
Here's a sketch of a simple derivation of the formula for counting symmetric $n\times n$ 0-1 matrices with every row and column distinct. (This is essentially the approach that Li and I took in our paper, though since we also covered the unlabeled case, there are more details.) This is equivalent to counting graphs, with loops allowed, such that no two vertices have the same neighborhood. Let $u_n$ be the number of such graph with vertex set $[n]=\{1,2,\dots,n\}$ and let $U(x) = \sum_{n=0}^\infty u_n x^n/n!$. Let $g_n=2^{n(n+1)/2}$ be the number of graphs (with loops allowed) on $[n]$ and let $G(x) = \sum_{n=0}^\infty g_n x^n/n!$. Every graph can be obtained from a graph with distinct neighborhoods by replacing each vertex with a nonempty set of vertices, all with the same neighborhood as the vertex they are replacing. Then by the properties of exponential generating functions, $G(x) = U(e^x-1)$. Substituting $\log(1+x)$ for $x$ gives $U(x) = G(\log(1+x))$ and expanding gives the formula for $u_n$ in terms of Stirling numbers of the first kind.
The same argument, with $2^{n(n-1)/2}$ instead of $2^{n(n+1)/2}$, counts graphs without loops with distinct neighborhoods (point-determining or mating graphs).
