## 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