March 2004
<<February March April>>
Part 1 Solution:
F(M,N) = 4 * (M+N-1)!/(M-1)!(N-1)! - 2*M*N
= 2N * ( 2 * Binomial(M+N-1,N) - M )
Let G(M,N) be the number of valid arrays whose top row is all 0. Each column is (M-c_i) 0's followed by (c_i) 1's, for some c_i between 0 and M-1 inclusive, and the integers c_i are weakly monotone. The number of non-decreasing N-tuples of integers between 0 and M-1 is Binomial(M+N-1,N): arrange M-1 blue tiles and N red tiles in a line, and for i=1,2,...,N let c_i be the number of blue tiles preceding the i-th red tile. The number of non-increasing N-tuples is the same. But if we add these two numbers, we double-count those sequences that are both non-increasing and non-decreasing, namely the constant
sequences (c,c,...,c), 0 \leq c \leq M-1, of which there are M. So adding the two numbers, and subtracting the double-count, we find that the number of valid arrays whose top row is all 0 is given by G(M,N) = 2*Binomial(M+N-1,N) - M.
Lemma:
Given a valid array, if we remove the left column, complement its elements (replace 0 by 1 and 1 by 0), and attach it to the right side, we obtain another valid array.
Proof of Lemma:
The new column is weakly monotone. If an old row was weakly monotone and started with 0, it must have been (k) 0's followed y (N-k) 1's, where 1 \leq k \leq N; in the new array, it is now (k-1) 0's followed by (N-k+1) 1's, still weakly monotone.
A similar argument holds if the old row started with 1.
We see that the number of valid arrays whose top row is (k) 0's followed by (N-k) 1's is the same as the number of valid arrays whose top row is all 0's, namely G(M,N); just apply the Lemma N-k times. In fact for each of 2N possible top rows, the number of valid arrays is again G(M,N). So we multiply G(M,N) by 2N, obtaining F(M,N) = 2N*(2*Binomial(M+N-1,N)-M).
Part 2 Solution:
Experimental: N by 3 array, entries from {0,1,2}, given by
F(3,N)=(19N^6 + 285N^5 + 1405N^4 + 2655N^3 + 736N^2 - 2940N + 900) / 180
= 17 + (N-1)(N+1)(N+2)(N+3)(19N^2+190N+360)/180
Notice that only the coefficient of N^1 is negative, and we had to define F(0)=5 to make it consistent.
Part 3 Solution:
Venkata Ramayya has provided an updated solution to Part 3. Click here to open the pdf file.
Part 4 Solution:
Gyozo Nagy showed that the problem in part 4 (the number of valid M by N by K arrays with elements from {0,1}) is closely related to a two-dimensional problem (the number of valid M by N arrays with elements from {0,1,...,K}). Given a valid M by N by K array, count the number of 1s in each line in the third direction (the line of length K), and enter that count into the corresponding cell of an M by N array. The resulting M by N array is again valid. One has to account for reflections (was the original line 0001111 or 1111000?). The details are left as an entertainment for the reader.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com