May 24th, 2008 admin
There is a matrix of numbers with n rows and m columns. The matrix consists of integers taking the value 1 through n. That is, at any given cell in the matrix the value is 1 or 2 or 3 or … or n. We want to find out how many such matrices exist in which you can always find n cells, one per row, that together have all the n unique integers in them.
Here is my approach and my solution to the problem. This solution has not been verified by Mau or anyone else, and there is a chance that I am missing some aspect of rigor required to make the proof watertight and, thus, self-verifying.
Approach
The space of all nxm matrices can be divided into a disjoint set of matrices that completely span the space. This disjoint set comprises
- matrices which have no row with all n numbers
- matrices which have exactly one row that contains all n numbers
- matrices which have exactly two rows that contain all the n numbers
… so on till
- matrices which have exactly n-1 rows that contain all the n numbers
- matrices which have each of the n rows containing all the n numbers
Now we can solve the problem for each subset that makes up the disjoint set that spans the space of mxn matrices, and add up the individual results. Interestingly, working backwards makes more sense to me. So let’s look at the subset of matrices which have all the n numbers in each of the n nows. There is no candidate matrix here that fails our criterion. All matrices will satisfy the criterion. Let’s call the set of matrices that satisfy the criterion, the set S and those that fail the criterion the set F. Therefore no matrix in this subset adds to F.
Next, let’s look at the subset of matrices which have all the n numbers in exactly n-1 rows. The remaining row, whatever be the number or numbers it carries, will cause the matrix to satisfy the criterion. Therefore no matrix in this subset adds to F.
Next, let’s look at the subset of matrices which have all the n numbers in exactly n-2 rows. The remaining 2 rows, will cause the overall matrix to fail, if they have no more than 1 number in them. That is they remaining two rows must be full of only one number. If a second number exists in either of the two rows, the matrix satisfies our criterion.
And so on.
So, the number of matrices in F is a sum of the following product over all values of i:
(how many ways can we select n-i rows)(how many ways can all n unique numbers show up in each of those selected rows)(how many ways can the remaining i rows contain, at most, i-1 unique numbers)
Solution
Basically, out of all possible matrices with n rows and m cols such that each element is an integer between 1 and n (both included), I try to figure out the number of matrices which do NOT satisfy the condition we are after, i.e., for these matrices you CANNOT select n elements, one on each row, such that the n elements are the n unique numbers, 1 through n. Call this set of matrices, which fail the condition, F (for fail). We are trying to find how many elements are in the set F.
The final answer for the number of matrices the satisfy the criteion, therefore, will be n^(n.m) – |F|, where |F| represents the cardinality of F, that is, the number of elements in set F.
To get to |F|, my line of thinking was:
F =
matrices for which there are, at most, n-1 unique numbers in the n rows
+ matrices for which there are, at most, n-2 unique numbers in n-1 rows and all n numbers in the remaining 1 row
+ matrices for which there are n-3 unique numbers in n-2 rows and all n numbers in the remaining 2 rows + … etc.
By ensuring that all the n numbers show up in the remaining x rows we are making sure that the matrix that satisfies a given term in the above summation does not satisfy the the previous term, and thus avoids being double counted.
Substituting terms,
+ …
As a summation, this can be written as
Here is how to understand each term in the summation above:
is the number ways can you choose n-i rows
is the number ways can you choose the n-i-1 numbers that will go into the selected n-i rows
is the number of ways can those (n-i).m elements in those n-i rows be filled with the chosen (n-i-1) numbers
is the number of ways we can guarantee that the remaining i rows each contain all the n elements.
Posted in Tidbits | No Comments »
