Ponder This Challenge - March 2004 - Number of weakly monotone arrays

Ponder This Challenge:

This month's puzzle comes from Yuval Dekel, based on work by Vladeta Jovovic and Vladimir Baltic.

A sequence of integers is "weakly monotone" if it is either non-decreasing or non-increasing. For example, there are exactly six weakly monotone sequences of length 3 whose elements are chosen from {0,1}, namely 000, 001, 011, 100, 110, 111.
The sequence 010 fails to be weakly monotone because it is not non-decreasing (a_2 > a_3) nor non-increasing (a_1 < a_2).

An M by N array of integers is "valid" if each of its rows and columns is weakly monotone.

Part 1:
Give, with proof, a formula (in terms of M and N) for the number of valid M by N arrays, with elements chosen from {0,1}.

Part 2:
Give, with proof, a formula (in terms of N) for the number of valid 3 by N arrays, with elements chosen from {0,1,2}.

Part 3:
Give, with proof, a formula (in terms of M and N) for the number of valid M by N arrays, with elements chosen from {0,1,2}.

Part 4:
Give, with proof, a formula (in terms of M, N and K) for the number of valid M by N by K arrays, with elements chosen from {0,1}.
(Here "valid" means that each line, in each of the three principal directions, is weakly monotone.)

We will accept submissions that solve (with proof) at least one part. Preference is given to closed-form solutions (no recursion, no sums, just binomial coefficients). Each proof is expected to be your own; it's no fair using a proof that you've seen elsewhere.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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

Solvers

• Gyozo Nagy (3.2.2004 @08:17:23 AM EDT)
• Narayanan Rajamani (3.2.2004 @11:15:14 PM EDT)
• Rustam Miftakhutdinov (3.3.2004 @03:00:52 AM EDT)
• Kalyana Chakravarthy (3.3.2004 @03:04:57 PM EDT)
• David Woodruff (3.4.2004 @11:09:07 PM EDT)
• Yeqi (3.6.2004 @06:47:35 AM EDT)
• Vladimir Sedach (3.7.2004 @03:59:17 PM EDT)
• Coserea Gheorghe (3.8.2004 @03:57:27 AM EDT)
• Luke Pebody (3.8.2004 @05:16:56 AM EDT)
• M Venkata Ramayya (3.9.2004 @12:08:31 AM EDT)
• Scott Hotes (3.9.2004 @03:26:42 AM EDT)
• Kalyana Chakravarthy (3.9.2004 @07:34:31 AM EDT)
• Aleksey Pinkin (3.10.2004 @02:33:00 PM EDT)
• John G Fletcher (3.10.2004 @07:38:58 PM EDT)
• Clive Tong (3.15.2004 @06:48:01 AM EDT)
• Tim Paulden (3.17.2004 @06:42:49 AM EDT)
• Gyozo Nagy (3.16.2004 @05:21:09 PM EDT)
• R. Nandakumar (3.17.2004 @11:18:00 PM EDT)
• Daniel Bitin (3.22.2004 @12:58:28 PM EDT)
• Andre Rzym (3.23.2004 @04:10:55 PM EDT)
• John G. Fletcher (3.23.2004 @11:43:50 PM EDT)
• M Venkata Ramayya (3.25.2004 @01:34:47 AM EDT)
• Derek Kisman (3.25.2004 @11:23:30 AM EDT)
• Samuel Hargestam (3.28.2004 @06:41:38 PM EDT)
• Sorin Ostafiev (3.29.2004 @05:58:37 AM EDT)
• Vincent Vermaut (3.30.2004 @07:43:48 AM EDT)
• IQSTAR (3.30.2004 @12:39:55 PM EDT)
• Dan Dima (3.31.2004 @12:22:25 PM EDT)
• Arun (3.31.2004 @12:43:47 PM EDT)
• Sivaramakrishnan (3.31.2004 @12:43:47 PM EDT)