How many ways are there to eat a chocolate bar?

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?

Solution 1:

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)$.

Example: $m=n=3$

We determine this way the number $p_{(3,3,3)}$ of possible ways to eat a $(3\times 3)$ chocolate bar which is according to OP's table \begin{align*} \color{blue}{p_{(3,3,3)}=1\,232} \end{align*} We start determining the $\binom{6}{3}=20$ valid paths. These are:

\begin{align*} &(0,0,0)\\ &(0,0,1)\,(0,1,1)\quad\quad\quad\quad\quad\quad\,\,\,\, (1,1,1)\\ &(0,0,2)\,(0,1,2)\,(0,2,2)\qquad\quad\,\,\,(1,1,2)\,(1,2,2)\qquad\quad\,\,\,(2,2,2)\\ &(0,0,3)\,(0,1,3)\,(0,2,3)\,(0,3,3)\,(1,1,3)\,(1,2,3)\,(1,3,3)\,(2,2,3)\,(2,3,3)\,(3,3,3) \end{align*}

We calculate iteratively $p_{(3,3,3)}$ by starting with $p_{(0,0,0)}=1$. We obtain \begin{align*} p_{(0,0,0)}&=1\\ \color{blue}{p_{(0,0,1)}}&=p_{(0,0,0)}\color{blue}{=1}\\ \color{blue}{p_{(0,0,2)}}&=p_{(0,0,1)}+p_{(0,0,0)}=1+1\color{blue}{=2}\\ \color{blue}{p_{(0,0,3)}}&=p_{(0,0,2)}+p_{(0,0,1)}+p_{(0,0,0)}=2+1+1\color{blue}{=4}\\ \\ \color{blue}{p_{(0,1,1)}}&=p_{(0,0,1)}+p_{(0,0,0)}=1+1\color{blue}{=2}\\ p_{(0,1,2)}&=p_{(0,1,1)}+p_{(0,0,1)}+p_{(0,0,0)}=2+1+1=4\\ p_{(0,1,3)}&=p_{(0,1,2)}+p_{(0,1,1)}+p_{(0,0,3)}=4+2+4=10\\ \color{blue}{p_{(0,2,2)}}&=p_{(0,1,2)}+p_{(0,1,1)}+p_{(0,0,2)}\\ &\quad+p_{(0,0,1)}+p_{(0,0,0)}=4+2+2+1+1\color{blue}{=10}\\ p_{(0,2,3)}&=p_{(0,2,2)}+p_{(0,1,3)}+p_{(0,0,3)}=10+10+4=24\\ \color{blue}{p_{(0,3,3)}}&=p_{(0,2,3)}+p_{(0,2,2)}+p_{(0,1,3)}+p_{(0,1,2)}\\ &\quad+p_{(0,1,1)}+p_{(0,0,3)}+p_{(0,0,2)}+p_{(0,0,1)}+p_{(0,0,0)}\\ &=24+10+10+4+2+4+2+1+1\color{blue}{=58}\\ \\ \color{blue}{p_{(1,1,1)}}&=p_{(0,1,1)}+p_{(0,0,1)}+p_{(0,0,0)}=2+1+1\color{blue}{=4}\\ p_{(1,1,2)}&=p_{(1,1,1)}+p_{(0,1,2)}+p_{(0,0,2)}=4+4+2=10\\ p_{(1,2,2)}&=p_{(1,1,2)}+p_{(1,1,1)}+p_{(0,2,2)}=10+4+10=24\\ p_{(1,1,3)}&=p_{(1,1,2)}+p_{(1,1,1)}+p_{(0,1,3)}+p_{(0,0,3)}=10+4+10+4=28\\ p_{(1,2,3)}&=p_{(1,2,2)}+p_{(1,1,3)}+p_{(0,2,3)}=24+28+24=76\\ p_{(1,3,3)}&=p_{(1,2,3)}+p_{(1,2,2)}+p_{(1,1,3)}+p_{(1,1,2)}+p_{(1,1,1)}\\ &=76+24+28+10+4+58=200\\ \\ \color{blue}{p_{(2,2,2)}}&=p_{(1,2,2)}+p_{(1,1,2)}+p_{(0,2,2)}+p_{(0,1,2)}+p_{(0,0,2)}\\ &\quad+p_{(1,1,1)}+p_{(0,1,1)}+p_{(0,0,1)}+p_{(0,0,0)}\\ &=24+10+10+4+2+4+2+1+1\color{blue}{=58}\\ p_{(2,2,3)}&=p_{(2,2,2)}+p_{(1,2,3)}+p_{(1,1,3)}\\ &\quad+p_{(0,2,3)}+p_{(0,1,3)}+p_{(0,0,3)}\\ &=58+76+28+24+10+4=200\\ p_{(2,3,3)}&=p_{(2,2,3)}+p_{(2,2,2)}+p_{(1,3,3)}+p_{(0,3,3)}\\ &=200+58+200+58=516\\ \\ \color{blue}{p_{(3,3,3)}}&=p_{(2,3,3)}+p_{(2,2,3)}+p_{(2,2,2)}+p_{(1,3,3)}+p_{(1,2,3)}\\ &\quad+p_{(1,2,2)}+p_{(1,1,3)}+p_{(1,1,2)}+p_{(1,1,1)}+p_{(0,3,3)}+p_{0,2,3)}\\ &\quad+p_{(0,2,2)}+p_{(0,1,3)}+p_{(0,1,2)}+p_{(0,1,1)}+p_{(0,0,3)}+p_{(0,0,2)}\\ &\quad+p_{(0,0,1)}+p_{(0,0,0)}\\ &=516+200+58+200+76+28+24+10+4+58\\ &\quad+24+10+10+4+2+4+2+1+1\\ &\,\,\color{blue}{=1\,232} \end{align*} and we obtain $p_{(3,3,3)}=1\,232$ according to OP's table. Entries with a rectangular shape are marked in blue. They are also given in OP's list.

Solution 2:

I would be pretty surprised if there were a nice answer. The related question of finding the number of linear extensions of a hypercube has no known nice formula, and there's no reason to expect one will ever be found; see for instance this paper discussing both Chomp and the linear extension problem.

Good asymptotic estimates are known in this case, though. For the boolean lattice linear extension problem, the "naive" graded linear extensions end up being a good estimate for all of them, and those have a simple product formula--the linked paper writes it out. Finding a good asymptotic estimate for your counts would likely be interesting. As a completely naive question, is the number of ordered antichains on the underlying rectangular poset a good estimate in a logarithmic sense, or is it woefully small?

For linear extensions, the trouble is the general problem is #P-complete, a classic result of Brightwell--Winkler. Even restricting to quite mild posets remains #P-complete; see this more recent paper of Dittmer--Pak. So, the only possible hope whatsoever of an efficient, explicit formula is for very particular posets. (Granted, the rectangular poset is very particular.)

My knowledge of this research area is relatively shallow, but I don't know of published results concerning the #P-completeness for Chomp. It would likely make a good paper. Igor Pak would probably be the person to ask. Who knows, you might even interest him in writing a paper on it?

Solution 3:

Before I start, I want highlight the following:

I think there could be a closed form for all $n,m$.

WLOG assume $n\ge m$. Let $F(n,m)$ be the solution to your problem for given $n,m\in\mathbb N$.

According to your data and the linked OEIS sequence, we have:

$$\begin{align} F(n,1)&=2^{n-1}\\ F(n,2)&=2\sum_{k=0}^{n} 4^k N(n, k)\\ \end{align}$$

Where $N(n,k)$ are Narayana numbers, given by:

$$ N(n, k) = \frac{1}{n}\binom{n}{k}\binom{n}{k+1} $$

Maybe a closed form for $m\ge3$ exists as well, in terms of summations of Narayana numbers.

Or perhaps some generalization of these numbers is needed.

Now that I've got that out of the way, below is a longer version of my comment.

This is not a complete answer, but is a long comment on the "exactly $b$ bites" polynomials.

I use nothing more than elementary counting. Perhaps someone else can make something out of this.

$1.)$ Manually solving individual polynomials $F_b$

Let $F_b(n,m)=F_b$ be the number of ways to eat the bar in exactly $b$ bites.

The solution to your problem is then given by:

$$ F(n,m)=\sum_{b=1}^{nm}F_b$$

The $b=1$ base case $F_1=1$, since there is only one possible (trivial) bite.

The problem is now finding a closed form for these polynomials $F_b$, where $b\in[1,nm]$.

Let the chocolate bar rectangle span from $(1,1)$ to $(n,m)$. For $b\ge2$, we have $(b-1)$ nontrivial bites. Imagine $i$th nontrivial bite $B_i$ as a rectangle with one corner at $(1,1)$ and the opposite corner at $(a_i,b_i)$. We need to sum over all of the possible ways to place these rectangles, such that when placing the corner $(a_i,b_i)$ of the next rectangle (bite) $B_i$, we do not place it into an already eaten square (square already contained within one of the previous bites).

When $b=2$, we have one nontrivial bite, which can be at any square except $(n,m)$.

$$F_2=-1+\sum_{a_1,b_1\gt0,0}^{n,m}1=nm-1$$

When $b=3$, we have two nontrivial bites. The second depends on the placement of the first.

After the first bite, we observe the second bite in one of the $3$ regions relative to the first bite.

$$\begin{align} F_3&=1+\sum_{a_1,b_1\gt0,0}^{n,m}\left( -1+ \sum_{a_2,b_2\gt a_1,b_1}^{n,m}1+ \sum_{a_2,b_2\gt 0,b_1}^{a_1,m}1+ \sum_{a_2,b_2\gt a_1,0}^{n,b_1}1 \right)\\ F_3&=\frac14\left(3 m^2 n^2-m^2 n-m n^2-5 m n+4\right) \end{align}$$

One is subtracted in the outer summation to remove the counted $(n,m)$ cases from the first inner summation, since that square belongs to the last bite. One is added to the entire result since the inner summation has one of $(-1)$'s extra, produced when $(a_1,b_1)=(n,m)$ in which case the first inner summation yields $0$. Finally, this gives the $F_3$ closed form.

In general, we can split the bar into regions depending on first $(b-1)$ bites, and then sum over those regions. The last bite is always $(n,m)$ square. We also need to subtract duplicates, etc.

I could continue individually solving $b=4,5,6,\dots$ But in general, I'm not sure how to find a closed form for all polynomials $F_b$.

Maybe someone else can take it from here.

$2.)$ Recursion for individual polynomials $F_b$

Alternatively, we can set up a recursion in $b$ that corresponds to this idea.

Let $b\ge1$ and let $(b+1)$th bite be the last bite. Let $f_{b-1}(t)$ be the total number of eaten squares after $(b-1)$th bite, of some biting sequence indexed $t$. Then the next-to-last bite, the $b$th bite, can be any of the uneaten squares (except the top-right corner square which is the last bite). That is, any of the $nm-1-f_{b-1}(t)$ squares. This gives a recursion in variable $b$:

$$\begin{align} F_{b+1}&=\sum_{t=1}^{F_b}\left(nm-1-f_{b-1}(t)\right)\\ F_{b+1}&=(nm-1)\cdot F_b-\sum_{t=1}^{F_b}f_{b-1}(t) \end{align}$$

Specially, $f_0(t)=0$ since the zeroth bite (no bites have been made yet) removes no squares.

The base case is $F_1=1$, since the only possible bite is the last bite.

We again give examples for first two cases, below:

For $b=1$, the recursion gives $F_2(n,m)=(nm-1)$, which makes sense, since first bite can be any of the $nm$ squares except the top-right corner, which is the last bite.

For $b=2$, we are observing the sum of $f_1(t)$ which goes over all possible removals of squares, given one bite. This is equivalent to observing all possible rectangles $a\times b$ within the original chocolate bar $n\times m$ rectangle, except the $n\times m$ rectangle itself. We can sum the areas of all of the rectangles:

$$ \sum_{a,b}R(a,b)=(1+2+\dots+n)(1+2+\dots+m)=\frac{n(n+1)}{2}\frac{m(m+1)}{2} $$

Then subtract the area of the $n\times m$ rectangle itself, $R(n,m)=nm$.

$$\begin{align} F_{3}&=(nm-1)\cdot(nm-1)-\sum_{t=1}^{nm-1}f_{1}(t) \\ F_{3}&=(nm-1)^2-\left( \frac{n(n+1)}{2}\frac{m(m+1)}{2}-nm\right)\\ F_{3}&=\frac14(3 m^2 n^2 - m^2 n - m n^2 - 5 m n + 4) \end{align}$$

Which gives the $b=2$ case closed form $F_3$, and agrees with our result from the first section.

To be able to solve the $F_{b+1}$ recursion, we need to find a closed form for:

$$ \lambda_{b-1}=\lambda_{b-1}(n,m)=\sum_{t=1}^{N_{b}}f_{b-1}(t) $$

That is, summing over all removed squares from all biting sequences of $b-1$ bites.

However, this looks equally hard as the starting problem.

Maybe someone else can take it from here.