IBM Ponder This #071 · March 2004

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.

Solution

Best opened after a real attempt

To be added.