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?
Best Answer
This is a starter providing some ideas which can be used to iteratively determine the number of ways to eat an $(m\times n)$ chocolate bar. We consider an $(m\times n)$ rectangle and start eating from bottom left to top right. The graphic below shows a valid configuration of a $(7\times 4)$ chocolate bar after three bite indicated by $X$.
Valid paths:
We characterize a valid path by an $n$-tupel giving for each $y$, $1\leq y\leq n$ the corresponding $x$-value , $1\leq x\leq m$. The valid path in the graphic is encoded this way as ${(1,2,2,5)}$. We have a total of $\binom{m+n}{n}$ valid paths and consider these paths as building blocks to determine the number of ways to eat the chocolate bar. A valid path is encoded as $(x_1,x_2,\ldots,x_n)$ with $0\leq x_1\leq \cdots \leq x_n\leq m$. The final path is $(m,m,\ldots,m)$.
In order to determine the number of ways to obtain $(1,2,2,5)$ we consider all possible predecessors from which we can get $(1,2,2,5)$ in one step. We add up the number of ways to obtain all predecessors and get so the number of ways for $(1,2,2,5)$. The predecessors of $(1,2,2,5)$ are indicated by the grey shaded regions and are \begin{align*} (\color{blue}{0},2,2,5)\qquad (1,2,2,\color{blue}{2})\\ (1,\color{blue}{1},2,5)\qquad (1,2,2,\color{blue}{3})\\ (1,\color{blue}{1},\color{blue}{1},5)\qquad (1,2,2,\color{blue}{4})\\ \end{align*} The blue marked coordinates are to bite off to come to $(1,2,2,5)$.