1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ It's a good idea to look up OEIS first. A088310 $\endgroup$
    – Brendan McKay
    Jun 29, 2015 at 13:23
  • $\begingroup$ For small $n$, I get the numbers of symmetric ones to be $4$, $44$, $716$, $24416$, which is a sequence not in the OEIS, nor are its obvious transforms (i.e. divide by 2 since we can swap 0/1). [Not sure why the question has 2 votes to close, as it seems perfectly reasonable to me.] $\endgroup$
    – Gordon Royle
    Jul 1, 2015 at 7:16

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
14
  • $\begingroup$ How do you get the count? $\endgroup$
    – Turbo
    Jun 29, 2015 at 14:13
  • $\begingroup$ Inclusion-exclusion but it's rather lenthty to post the proof here. I'll look at the symmetric case later. $\endgroup$
    – Max Alekseyev
    Jun 29, 2015 at 14:15
  • $\begingroup$ ok is there 'main idea(s)' for the formula? $\endgroup$
    – Turbo
    Jun 29, 2015 at 14:20
  • 1
    $\begingroup$ If one fix a permutation of rows $\pi$ and a permutation of columns $\sigma$, then the number of matrices invariant w.r.t. $\pi$ and $\sigma$ equals $k^{i\cdot j}$, where $i$ and $j$ are the number of cycles in $\pi$ and $\sigma$, respectively. $\endgroup$
    – Max Alekseyev
    Jun 29, 2015 at 14:39
  • 1
    $\begingroup$ A closely related problem is that of counting graphs in which no two vertices have the same neighborhood. This corresponds to symmetric 0-1 matrices with 0s on the diagonal. These graphs are called point-determining or mating graphs. You can find links to their enumeration (both labeled and unlabeled) at oeis.org/A006024. $\endgroup$
    – Ira Gessel
    Feb 23, 2019 at 19:48
4
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.