I'm teaching an intro programming course and came up with a recursion problem for my students to solve that's inspired by the game Chomp. Here's the problem statement:
You have a chocolate bar that’s subdivided into individual squares. You decide to eat the bar according to the following rule: if you choose to eat one of the chocolate squares, you have to also eat every square below and/or to the right of that square.
For example, here’s one of the many ways you could eat a 3 × 5 chocolate bar while obeying the rule. The star at each step indicates the square chosen out of the chocolate bar, and the gray squares indicate which squares must also be eaten in order to comply with the above rule.
The particular choice of the starred square at each step was completely arbitrary, but once a starred square is picked the choice of grayed-out squares is forced. You have to eat the starred square, plus each square that’s to the right of that square, below that square, or both. The above route is only one way to eat the chocolate bar. Here’s another:
As before, there’s no particular pattern to how the starred squares were chosen, but once we know which square is starred the choice of gray squares is forced.
Now, given an $m \times n$ candy bar, determine the number of different ways you can eat the candy bar while obeying the above rule.
When I gave this to my students, I asked them to solve it by writing a recursive function that explores all the different routes by which the chocolate bar could be eaten. But as I was writing this problem, I started wondering - is there a closed-form solution?
I used my own solution to this problem to compute the number of different sequences that exist for different values of $m$ and $n$, and here's what I found:
$$\left(\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 2 & 4 & 8 & 16 & 32\\ 1 & 2 & 10 & 58 & 370 & 2514 & 17850\\ 1 & 4 & 58 & 1232 & 33096 & 1036972 & 36191226\\ 1 & 8 & 370 & 33096 & 4418360 & 768194656 & 161014977260\\ 1 & 16 & 2514 & 1036972 & 768194656 & 840254670736 & 1213757769879808\\ 1 & 32 & 17850 & 36191226 & 161014977260 & 1213757769879808 & 13367266491668337972 \end{matrix}\right)$$
Some of these rows show nice patterns. The second row looks like it's all the powers of two, and that makes sense because if you have a $1 \times n$ chocolate bar then any subsequence of the squares that includes the first square, taken in sorted order, is a way to eat the candy bar. The third row shows up as A086871 on the OEIS, but none of the rows after that appear to be known sequences. The diagonal sequence also isn't on the OEIS,
I believe that this problem is equivalent to a different one:
Consider the partial order defined as the Cartesian product of the less-than relation over the sets $[m] = \{0, 1, 2, ..., m - 1\}$ and $[n]$. How many distinct sequences of elements of this partial order exist so that no term in the sequence is dominated by any previous element and the final element is the maximum element of the order?
I'm completely at a loss for how to determine the answer to that question.
Is there a nice closed-form solution to this problem?