Problem:
How many arrays whose entries are s and s are there such that the row sums (the sum of the entries in each row) are , and , in some order, and the column sums (the sum of the entries in each column) are also , and , in some order? For example, the array
satisfies the condition.
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Because one of the row sums is 4 and one of the column sums is 4 , there must be a row of all 1 s and a column of all 1 s . There are ways to choose which row and which column are all 1s. After excluding this row and column, the remaining matrix has row sums and column sums of 0,1 , and 2 . Furthermore, each of 0,1 , and 2 appears exactly once as a row sum and once as a column sum in this array. There are now 3 ways to choose which row has two ways to choose which entries in that row have 1 s , and 4 ways to choose where the remaining 1 goes in order to get the required column sums. Therefore the number of such matrices is .
More generally, for matrices of 0 s and 1 s such that the set of sums of the entries of the rows equals the set and the set of sums of the entries of the columns equals the set , the rows and columns of the matrix can be permuted to produce the matrix that has in the th row and in the th column for . These permutations do not change the set of row sums or the set of column sums. Conversely, any permutation of the rows and columns of will produce a different matrix satisfying the row-sum and column-sum condition. Because there are ! ways to permute the rows of and ! ways to permute the columns of , the number of such matrices is . For the number of such matrices is .
Note: The answer to this problem (generalized to matrices) is the same as the answer to a problem from the 2022 AIME I about counting sequences of colored blocks such that there are an even number of blocks between each pair of blocks of the same color, and this is not a coincidence. See sequence A001044 in the On-Line Encyclopedia of Integer Sequences.
The problems on this page are the property of the MAA's American Mathematics Competitions