Skip to main content
added symmetric case
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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.

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.

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.

added 24 characters in body
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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 2^{i\cdot j},$$$$\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.

For generic (not necessarily symmetric) $m\times n$ matrices, 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 2^{i\cdot j},$$ where $s(,)$ are Stirling numbers of first kind with sign.

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.

Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

For generic (not necessarily symmetric) $m\times n$ matrices, 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 2^{i\cdot j},$$ where $s(,)$ are Stirling numbers of first kind with sign.