Sequences and Tables

We may apply the Gale-Ryser theorem to this problem. It states: Let $p, q$ be partitions of a positive integer. Then there exists a $(0,1)$ -matrix $X$ such that $c(X)=p, r(X)=q$ if and only if $q$ is dominated by $p^*$ . Here, $c(X)$ and $r(X)$ refer to the sum of all the column vectors of $X$ and the sum of all the row vectors of $X$ respectively (i.e. the $i^{th}$ element of $c(X)$ and $j^{th}$ element of $r(X)$ represent the sum of the elements in row $i$ and column $j$ of $X$ respectively), while $p^*$ represents the conjugate partition of $p$ . We shall reproduce a simple proof of this theorem by Krause below.

The necessity of the dominance condition is easily proved. Let $X$ be a $k \times l$ $(0,1)$ -matrix $(x_{ij})$ such that $c(X)=p, r(X)=q$ . If $X$ does not contain gaps (i.e. there are no $i \leq k$ , $j < h \leq l$ such that $x_{ij} = 0$ and $x_{ih} = 1$ ), then $X$ is a Ferrers matrix and $p^* = q$ . Now let $(i,j)$ be a gap of $X$ and let $h > j$ be maximal such that $x_{ih}=1$ . Swapping $x_{ij}$ and $x_{ih}$ , we obtain a matrix $X'$ such that $c(X')=p$ and the number of gaps of $X'$ is lower than the number of gaps of $X$ . It is easy to see that $r(X')$ dominates $r(X)$ , so it follows by induction on the number of gaps that $p^*$ dominates $q$ .

We now need to prove the sufficiency of the dominance condition for the existence for the matrix $X$ such that $c(X)=p$ and $r(X)=q$ . Let $p=(p_1,…,p_k)$ and $q=(q_1,…,q_l)$ be partitions of a positive integer $u$ such that $p^*$ dominates $q$ . First we observe that there is a $k \times l$ $(0,1)$ -matrix $Y$ such that $c(B) = p$ and $r(B)$ dominates $q$ , namely the Ferrers matrix for $p$ with $l-p_1$ columns of zeros adjoined. Thus, it suffices to prove the following claim: Given a $k \times l$ $(0,1)$ -matrix $X$ such that $c(X) = p$ , $r(X)$ dominates $q$ and $r(X) \neq q$ , we can find a $k \times l$ $(0,1)$ -matrix $X'$ such that $c(X')=p$ , $r(X')$ dominates $q$ , and $\|r(X')-q\| <\|r(X)-q\|$ (where $\| \|$ is the ordinary Euclidean norm). If this claim is true, then we can apply this repeatedly and we will eventually find a $(0,1)$ -matrix $X$ such that $c(X) = p$ and $\|r(X)-q\| = 0$ (i.e. $r(X) = q$ ), since $\|r(X)-q\|^2$ is an integer which decreases in each step. The proof of this claim is as follows. Let $r(X) = (r_1,…,r_l)$ . Let $i$ be minimal such that $r_i > q_i$ , and let $j$ be minimal such that $r_j < q_j$ . Then $i < j$ , since $r(X)$ dominates $q$ . Also, we have $r_i - 1 \geq q_i \geq q_j \geq r_j+1$ , i.e. $r_i-r_j \geq 2$ . Define the vector $r' = (r_1',…r_l')$ , with $r_i' = r_i - 1$ , $r_j' = r_j + 1$ and $r_a' = r_a$ if $a \neq i,j$ . Since $(r_i - 1)^2+(r_j + 1)^2 = r_i^2 + r_j^2 - 2(r_i - r_j -1) > r_i^2 + r_j^2$ , then we have $\|r'-q\| < \|r-q\|$ . Moreover, $q$ is dominated by $r'$ , as $r_s' \geq q_s$ for all $s < j$ and $r_1'+…+r_s' = r_1+…+r_s \geq q_1 + … + q_s$ for all $s \geq j$ . Since $r_i-r_j \geq 2$ , we can find a row index $h$ (in fact, there are at least two) such that $x_{hi} = 1$ and $x_{hj} = 0$ . For any such $h$ , the matrix $X' = (x_{ab}')$ defined by swapping $x_{hi}$ and $x_{hj}$ has a row vector sum $r'$ and column vector sum $p$ . This completes the proof of the claim, and therefore we have also proven the sufficiency of the dominance condition.

Now that we have proven the Gale-Ryser theorem, we may apply it to solve the problem. Clearly, for all $(A,B)$ satisfying the conditions in the question, the sum of the elements in $A$ and $B$ are the same - both are equal to the sum of the elements of the corresponding table. Thus, we may see $A$ and $B$ as partitions of the same positive integer $u$ , where $u$ may take any value from $1$ to $6$ . The Gale-Ryser theorem states that this is equivalent to saying that $A^*$ dominates $B$ . So we just need to find the number of such pairs of sequences $(A,B)$ .

All the partitions of the integers from $1$ to $6$ are as listed.

$1: (1) \\ 2: (2), (1,1) \\ 3: (3), (2, 1), (1,1,1) \\ 4: (4), (3,1), (2,2), (2,1,1), (1,1,1,1) \\ 5: (5), (4,1), (3,2), (3,1,1), (2,2,1), (2,1,1,1), (1,1,1,1,1) \\ 6: (6), (5,1), (4,2), (3,3), (4,1,1), (3,2,1), (2,2,2), (3,1,1,1), (2,2,1,1), (2,1,1,1,1), (1,1,1,1,1,1)$

It is easy to check that for each number, each partition dominates itself and all the ones after it, with the exception of two pairs with no dominance relationship: $(3,3)$ and $(4,1,1)$ ; and $(2,2,2)$ and $(3,1,1,1)$ .

Consider a fixed positive integer $u$ from $1$ to $6$ . Then $A$ may be chosen from the set of partitions corresponding to the integer $u$ . In fact, $A^*$ will also be one of the partitions in the same set. There is clearly a one-to-one correspondence of the set of partitions $A$ and the set of conjugate partitions $A^*$ , so the latter set also spans the entire set of partitions of $u$ and each $A^*$ corresponds to exactly one $A$ . Thus, for each $u$ , we just need to count how many pairs $(A^*,B)$ satisfy $A^*$ dominates $B$ , where both $A^*$ and $B$ are (not necessarily distinct) partitions chosen from the set of partitions corresponding to the integer $u$ . This is easy, because we already checked earlier that, with the exception of two pairs of partitions, the rest of the pairs of partitions within the same set have the property that one of them dominates another – so we can assign the partition that dominates the other as $A^*$ and the other as $B$ . The number of ways we can do this is $0 + {2 \choose 2} + {3 \choose 2} + {5 \choose 2} + {7 \choose 2} + {11 \choose 2} - 2 = 88$ . But we have not counted the ways that $A^* = B$ , so we need to add $1+2+3+5+7+11=29$ to get $117$ .

Here we will furnish a short proof of this result (this proof is easily found on the internet)

Gale-Ryser theorem: the (0,1) matrix exists iff the sequence B' dominates A. B' is defined as B' 1, B' 2 ..., where B' i is the number of elements in B with values larger than or equal to i, B' i > 0. For instance, if B is {3,1,1,1}, B' is {4,1,1}, if B is {3,2,1}, B' is {3,2,1}

Note that if this result is true, simple checking gives us 117 as an answer. (this can be sped up by splitting cases based on the sum of A and B - for instance, there is 1 sequence with sum 1, 2 with sum 2, 3 with sum 3, 5 with sum 4, 7 with sum 5, 11 with sum 6, which only leaves us 209 pairs to check, most of which are trivial)

We can assume that A and B have the same sum. Now assume that B' does not dominate A. This implies that for some m, B' 1 + B' 2 ... + B' m is less than A 1 + A 2 ... + A m. Considering the first m rows, it is clear that the number of 1's is at most B' 1 + B' 2 ... + B'_m; which gives you the necessity part of the theorem (the easy part).

Now we prove that as long as B' dominates A, such a matrix will exist. We prove this as follows:

Given a (0,1) matrix with column sums B, with its row sums defining a sequence A' which dominates A, and A' not equal to A, we aim to create a new matrix with the same column sums, with row sums defining A'' which still dominates A, but with the following change:

the quantity ||A''-A|| < ||A'-A|| decreases, where || || represents the normal euclidean norm - denote this as the 'distance' between the two sequences

(note: euclidean norm refers to the sum of absolute values of differences between terms of the two sequences. for example, if A' = {4,2,0} and A = {2,2,2}, ||A'-A|| = |4-2| + |2-2| + |0-2| = 4)

It is clear that this monovariant (distance) is a non-negative integer, so if we can show that the creation of this 'improved' matrix is always possible, the monovariant quantity will eventually reach 0, which will give us the desired matrix.

Let i be minimal such that A'' i > A i, and let j be minimal such that A'' j < A j. Because A'' dominates A, the existence of i and j is guaranteed; furthermore, i < j.

Clearly, if we take A'' and replace A'' i and A'' j with A"' i - 1 and A'' j-1 respectively, That resulting sequence will have a shorter distance to A.

Observe that row i has more '1's then row j (since A'' i > A i >= A j > A'' j) Thus we can move a '1' in a column from row i to row j, for some column. This completes our proof of the result.