If you consider all $10$ by $15$ matrices with entries that are either $0$ or $1$, there are ${2^{15} \choose 10}$ with no repeated rows (up to row permutation) and ${2^{10} \choose 15}$ with no repeated columns (up to column permutation). How many are there with neither any repeated rows or columns (up to either row or column permutation)?
[Math] Number of matrices with no repeated columns or rows
combinatoricsmatrices
Best Answer
This can actually be worked out in a much more straight-forward manner than it seems, through a bit of reasoning.
Suppose that we construct a $10\times15$ matrix such that there are no repeated columns. Now, we must necessarily have that the number of repeated rows is somewhere between 0 and 9 (assuming that one row has to be "unique" first before there is a repeat). And so, we go about finding the number of possibilities for each repeat-count starting with the highest.
It is easy enough to see that there cannot be 9 repeats, as that would require all 15 columns to be either all-zeros or all-ones, and thus at most two would be "unique". Similarly, with 8 repeats, there would be only two "unique" rows, and thus only four possible columns. We can say the same thing about 7 repeats, which would provide only eight possible columns. Thus, we begin with the case of 6 repeats.
If there are 6 repeats, then there are four "unique" rows. In order to satisfy the conditions, these four "unique" rows must contain 15 of the 16 possible 4-bit combinations. The remaining 6 rows can be chosen from amongst the four "unique" rows.
If there are 5 repeats, then there are five "unique" rows, and we can find the number of these by observing that this is proportional to the number of $5\times15$ matrices with no repeated column, for which there are no repeating rows (and thus you subtract off a number proportional to the one we obtained for 6 repeats).
This can then be repeated until we get to $10\times15$, by working out how many $n\times15$ matrices can be made without repeats based on the value for $n-1$.
With the $n\times15$ case, there are ${2^n}\choose{15}$ possible matrices (up to column permutation). From these, we must subtract off the number of matrices that have $k$ repeated rows, with $k$ running from $1$ to $n-4$. We will call the number of $n\times15$ matrices without repeats $M_n$.
Now, we can see that $$ M_n ={2^n\choose15} - \sum_{k=4}^{n-1} S(n,k)M_k $$ where $S(n,k)$ is a Stirling number of the second kind. This is because we are partitioning our set of $n$ rows into non-empty subsets such that there are $k$ unique subsets, and for which order is irrelevant (that is, we take the subset containing the first row to be subset "1", then the subset containing the first row not in the first subset to be subset "2", and so on).
Now, we can do our calculations...
$$ M_4 = {16\choose15}\\ M_5 = {32\choose15} - S(5,4) M_4 = {32\choose15} - 10\times 16\\ M_6 = {64\choose15} - S(6,4) M_4 - S(6,5) M_5 = {64\choose15} - 65 M_4 - 15 M_5\\ \vdots $$ and so on.
Once you have $M_{10}$, you must finish the process by dividing out the possible row permutations - that is, divide by $10!$. Of course, the actual number is going to be very close to ${2^{10}\choose15}/10!$, as one would expect repeats to be far less common than non-repeats.
(Through use of a spreadsheet, I find that the number is roughly $2.709912\times10^{26}$, although some small truncation error may have made its way into that expression)